0020. 有效的括号 · ttttt

# 0020. 有效的括号 ## 题目地址(20. 有效的括号) <https://leetcode-cn.com/problems/valid-parentheses/description> ## 题目描述 ``` <pre class="calibre18">``` 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1: 输入: "()" 输出: true 示例 2: 输入: "()[]{}" 输出: true 示例 3: 输入: "(]" 输出: false 示例 4: 输入: "([)]" 输出: false 示例 5: 输入: "{[]}" 输出: true ``` ``` ## 前置知识 - [栈](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 百度 - 腾讯 - 字节 - airbnb - amazon - bloomberg - facebook - google - microsoft - twitter - zenefits ## 栈 ### 思路关于这道题的思路，邓俊辉讲的非常好，没有看过的同学可以看一下，[视频地址](http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184+sp/courseware/ad1a23c053df4501a3facd66ef6ccfa9/8d6f450e7f7a445098ae1d507fda80f6/)。使用栈，遍历输入字符串如果当前字符为左半边括号时，则将其压入栈中如果遇到右半边括号时，分类讨论： 1）如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环 2）若此时栈为空，则直接返回 false 3）若不为对应的左半边括号，反之返回 false ![](https://img.kancloud.cn/d7/3a/d73a226d8329befb1f16533545257b33_960x540.gif) （图片来自： <https://github.com/MisterBooo/LeetCodeAnimation>) > 值得注意的是，如果题目要求只有一种括号，那么我们其实可以使用更简洁，更省内存的方式 - 计数器来进行求解，而不必要使用栈。 > > 事实上，这类问题还可以进一步扩展，我们可以去解析类似 HTML 等标记语法，比如 ### 关键点解析 1. 栈的基本特点和操作 2. 如果你用的是 JS 没有现成的栈，可以用数组来模拟入： push 出：pop > 入： push 出 shift 就是队列 ### 代码代码支持：JS，Python Javascript Code: ``` <pre class="calibre18">``` /** * @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: ``` <pre class="calibre18">``` 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 ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(N)O(N)O(N) ## O(1) 空间 ### 思路基本思路是修改参数，将参数作为我们的栈。随着我们不断遍历， s 慢慢变成了一个栈。因此 Python，Java，JS 等**字符串不可变**的语言无法使用此方法达到 O(1)O(1)O(1)。具体参考： [No stack O(1) space complexity O(n) time complexity solution in C++](https://leetcode.com/problems/valid-parentheses/discuss/9478/No-stack-O(1)-space-complexity-O(n)-time-complexity-solution-in-C++/244061>) ### 代码代码支持：C++ C++: ``` <pre class="calibre18">``` 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(N)O(N) - 空间复杂度：O(1)O(1)O(1) ## 正则匹配 ### 思路我们不断通过消除 '\[\]' ， '()', '{}' ，最后判断剩下的是否是空串即可，就像开心消消乐一样。 ### 代码代码支持：Python，JavaScript Python: ``` <pre class="calibre18">``` class Solution: def isValid(self, s): while '[]' in s or '()' in s or '{}' in s: s = s.replace('[]','').replace('()','').replace('{}','') return not len(s) ``` ``` JavaScript: ``` <pre class="calibre18">``` 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; }; ``` ``` **复杂度分析** - 时间复杂度：取决于正则引擎的实现 - 空间复杂度：取决于正则引擎的实现 ## 相关题目 - [32. 最长有效括号](32.longest-valid-parentheses.html) ## 扩展 - 如果让你检查 XML 标签是否闭合如何检查，更进一步如果要你实现一个简单的 XML 的解析器，应该怎么实现？更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)