题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
难度：Middle
前置知识
公司
- 阿里
- 百度
- 腾讯
- 字节
- airbnb
- amazon
- bloomberg
- microsoft
- zenefits
栈
思路
关于这道题的思路，邓俊辉讲的非常好，没有看过的同学可以看一下，视频地址。
使用栈，遍历输入字符串
如果当前字符为左半边括号时，则将其压入栈中
如果遇到右半边括号时，分类讨论：
1）如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环
2）若此时栈为空，则直接返回 false
3）若不为对应的左半边括号，反之返回 false
（图片来自： https://github.com/MisterBooo/LeetCodeAnimation)
值得注意的是，如果题目要求只有一种括号，那么我们其实可以使用更简洁，更省内存的方式 – 计数器来进行求解，而不必要使用栈。
关键点解析
- 栈的基本特点和操作
- 如果你用的是 JS 没有现成的栈，可以用数组来模拟。
比如 入： push 出：pop 就是栈。 入： push 出 shift 就是队列。 但是这种算法实现的队列在头部删除元素的时候时间复杂度比较高，具体大家可以参考一下双端队列 deque。
代码
代码支持：JS，Python
Javascript Code:
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
* @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
复杂度分析
- 时间复杂度：$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)
JavaScript:
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链接：20.valid-parentheses
更多题解可以访问我的 码农周刊 仓库：https://github.com/meibin08/free-programming-books， 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发，我想请你帮我两个小忙：
- 把这篇文章分享给你的朋友 / 交流群，让更多的人看到，一起进步，一起成长！
- 关注公众号 「画漫画的程序员」，公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有，如若转载，请注明出处
转载请注明：文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com
微信扫一扫 
admin 
