题目地址
https://leetcode.com/problems/valid-parentheses/description
题目描述
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
思路
关于这道题的思路,邓俊辉讲的非常好,没有看过的同学可以看一下, 视频地址。
使用栈,遍历输入字符串
如果当前字符为左半边括号时,则将其压入栈中
如果遇到右半边括号时,分类讨论:
1)如栈不为空且为对应的左半边括号,则取出栈顶元素,继续循环
2)若此时栈为空,则直接返回false
3)若不为对应的左半边括号,反之返回false
(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)
值得注意的是,如果题目要求只有一种括号,那么我们其实可以使用更简洁,更省内存的方式 - 计数器来进行求解,而
不必要使用栈。
事实上,这类问题还可以进一步扩展,我们可以去解析类似HTML等标记语法, 比如
关键点解析
- 栈的基本特点和操作
- 如果你用的是JS没有现成的栈,可以用数组来模拟
入: push 出: pop
入: push 出 shift 就是队列
代码
- 语言支持:JS,Python
Javascript Code:
/* * @lc app=leetcode id=20 lang=javascript * * [20] Valid Parentheses * * https://leetcode.com/problems/valid-parentheses/description/ * * algorithms * Easy (35.97%) * Total Accepted: 530.2K * Total Submissions: 1.5M * Testcase Example: '"()"' * * Given a string containing just the characters '(', ')', '{', '}', '[' and * ']', determine if the input string is valid. * * An input string is valid if: * * * Open brackets must be closed by the same type of brackets. * Open brackets must be closed in the correct order. * * * Note that an empty string is also considered valid. * * Example 1: * * * Input: "()" * Output: true * * * Example 2: * * * Input: "()[]{}" * Output: true * * * Example 3: * * * Input: "(]" * Output: false * * * Example 4: * * * Input: "([)]" * Output: false * * * Example 5: * * * Input: "{[]}" * Output: true * * */ /** * @param {string} s * @return {boolean} */ var isValid = function(s) { let valid = true; const stack = []; const mapper = { '{': "}", "[": "]", "(": ")" } for(let i in s) { const v = s[i]; if (['(', '[', '{'].indexOf(v) > -1) { stack.push(v); } else { const peak = stack.pop(); if (v !== mapper[peak]) { return false; } } } if (stack.length > 0) return false; return valid; };
Python Code:
class Solution:
def isValid(self,s):
stack = []
map = {
"{":"}",
"[":"]",
"(":")"
}
for x in s:
if x in map:
stack.append(map[x])
else:
if len(stack)!=0:
top_element = stack.pop()
if x != top_element:
return False
else:
continue
else:
return False
return len(stack) == 0
扩展
如果让你检查XML标签是否闭合如何检查, 更进一步如果要你实现一个简单的XML的解析器,应该怎么实现?
LeetCode题解计算机为什么是基于二进制的?可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈
LeetCode题解10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。要求用程序模拟十万次,暴力求出该概率来自:字节跳动 算法工程师一面的第一题 (3月30日,60分钟,牛客网视频面)https://www.nowcoder.com/discuss/395924
LeetCode题解微信红包微信红包 如何分配 让每个人在数学期望上是一样的?在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。 它反映随机变量平均取值的大小。 需要注意的是,期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。 期望值是该变量输出值的平均数。