0020. 有效的括号
题目地址(20. 有效的括号)
https://leetcode-cn.com/problems/valid-parentheses/description
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1:输入: "()"输出: true示例 2:输入: "()[]{}"输出: true示例 3:输入: "(]"输出: false示例 4:输入: "([)]"输出: false示例 5:输入: "{[]}"输出: true前置知识
公司
阿里
百度
腾讯
字节
airbnb
amazon
bloomberg
facebook
google
microsoft
twitter
zenefits
栈
思路
关于这道题的思路，邓俊辉讲的非常好，没有看过的同学可以看一下，视频地址。
使用栈，遍历输入字符串
如果当前字符为左半边括号时，则将其压入栈中
如果遇到右半边括号时，分类讨论：
1）如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环
2）若此时栈为空，则直接返回 false
3）若不为对应的左半边括号，反之返回 false
（图片来自： https://github.com/MisterBooo/LeetCodeAnimation)
值得注意的是，如果题目要求只有一种括号，那么我们其实可以使用更简洁，更省内存的方式 - 计数器来进行求解，而不必要使用栈。 而之所以多种括号不可以使用计数器在 $O(1)$ 空间做到是因为类似这种用例会无法处理 "([)]"。
关键点解析
栈的基本特点和操作
可以用数组来模拟栈
比如 入： push 出：pop 就是栈。 入： push 出 shift 就是队列。 但是这种算法实现的队列在头部删除元素的时候时间复杂度比较高，具体大家可以参考一下双端队列 deque。
代码
代码支持：JS，Python，Java，C++
Javascript Code:
/** * @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) == 0Java Code:
class Solution { public boolean isValid(String s) { //1.判断空字符串 if(s.isEmpty()) return true; //2.创建辅助栈 Stack<Character> stack = new Stack<>(); //3.仅遍历一次 for(char c : s.toCharArray()){ if(c == '('){ stack.push(')'); }else if(c == '['){ stack.push(']'); }else if(c == '{'){ stack.push('}'); }else if(stack.isEmpty() || c != stack.pop()){ return false; } } //4.返回 return stack.isEmpty(); }}C++ Code:
class Solution {public: bool isValid(string s) { int n = s.size(); if (n % 2 == 1) { return false; } unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; stack<char> stk; for (char ch: s) { if (pairs.count(ch)) { if (stk.empty() || stk.top() != pairs[ch]) { return false; } stk.pop(); } else { stk.push(ch); } } return stk.empty(); }};复杂度分析
时间复杂度：$O(N)$
空间复杂度：$O(N)$
O(1) 空间
思路
基本思路是修改参数，将参数作为我们的栈。 随着我们不断遍历， s 慢慢变成了一个栈。
因此 Python，Java，JS 等字符串不可变的语言无法使用此方法达到 $O(1)$。
具体参考：No stack O(1) space complexity O(n) time complexity solution in C++
代码
代码支持：C++
C++:
class Solution {public: bool isValid(string s) { int top = -1; for(int i =0;i<s.length();++i){ if(top<0 || !isMatch(s[top], s[i])){ ++top; s[top] = s[i]; }else{ --top; } } return top == -1; } bool isMatch(char c1, char c2){ if(c1 == '(' && c2 == ')') return true; if(c1 == '[' && c2 == ']') return true; if(c1 == '{' && c2 == '}') return true; return false; }};复杂度分析
时间复杂度：$O(N)$
空间复杂度：$O(1)$
正则匹配
思路
我们不断通过消除 '[]' ， '()', '{}' ，最后判断剩下的是否是空串即可，就像开心消消乐一样。
代码
代码支持：Python，JavaScript
Python:
class Solution: def isValid(self, s): while '[]' in s or '()' in s or '{}' in s: s = s.replace('[]','').replace('()','').replace('{}','') return not len(s)#"false">
var isValid = function (s) { while (s.includes("[]") || s.includes("()") || s.includes("{}")) { s = s.replace("[]", "").replace("()", "").replace("{}", ""); } s = s.replace("[]", "").replace("()", "").replace("{}", ""); return s.length === 0;};复杂度分析
时间复杂度：取决于正则引擎的实现
空间复杂度：取决于正则引擎的实现
相关题目
扩展
如果让你检查 XML 标签是否闭合如何检查， 更进一步如果要你实现一个简单的 XML 的解析器，应该怎么实现？
事实上，这类问题还可以进一步扩展，我们可以去解析类似 HTML 等标记语法， 比如
<p></p> <body></body>
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
