0020. 有效的括号
题目地址(20. 有效的括号)
题目描述
1
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
2
3
有效字符串需满足：
4
5
左括号必须用相同类型的右括号闭合。
6
左括号必须以正确的顺序闭合。
7
注意空字符串可被认为是有效字符串。
8
9
示例 1:
10
11
输入: "()"
12
输出: true
13
示例 2:
14
15
输入: "()[]{}"
16
输出: true
17
示例 3:
18
19
输入: "(]"
20
输出: false
21
示例 4:
22
23
输入: "([)]"
24
输出: false
25
示例 5:
26
27
输入: "{[]}"
28
输出: true
Copied!
前置知识
公司
- 阿里
- 百度
- 腾讯
- 字节
- airbnb
- amazon
- bloomberg
- facebook
- google
- microsoft
- twitter
- zenefits
栈
思路
使用栈，遍历输入字符串
如果当前字符为左半边括号时，则将其压入栈中
如果遇到右半边括号时，分类讨论：
1）如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环
2）若此时栈为空，则直接返回 false
3）若不为对应的左半边括号，反之返回 false
20.validParentheses
值得注意的是，如果题目要求只有一种括号，那么我们其实可以使用更简洁，更省内存的方式 - 计数器来进行求解，而不必要使用栈。 而之所以多种括号不可以使用计数器在 $O(1)$ 空间做到是因为类似这种用例会无法处理 "([)]"。
关键点解析
- 1.栈的基本特点和操作
- 2.可以用数组来模拟栈
代码
代码支持：JS，Python
Javascript Code:
1
/**
2
* @param {string} s
3
* @return {boolean}
4
*/
5
var isValid = function (s) {
6
let valid = true;
7
const stack = [];
8
const mapper = {
9
"{": "}",
10
"[": "]",
11
"(": ")",
12
};
13
14
for (let i in s) {
15
const v = s[i];
16
if (["(", "[", "{"].indexOf(v) > -1) {
17
stack.push(v);
18
} else {
19
const peak = stack.pop();
20
if (v !== mapper[peak]) {
21
return false;
22
}
23
}
24
}
25
26
if (stack.length > 0) return false;
27
28
return valid;
29
};
Copied!
Python Code:
1
class Solution:
2
def isValid(self,s):
3
stack = []
4
map = {
5
"{":"}",
6
"[":"]",
7
"(":")"
8
}
9
for x in s:
10
if x in map:
11
stack.append(map[x])
12
else:
13
if len(stack)!=0:
14
top_element = stack.pop()
15
if x != top_element:
16
return False
17
else:
18
continue
19
else:
20
return False
21
return len(stack) == 0
Copied!
复杂度分析
- 时间复杂度：$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++](https://leetcode.com/problems/valid-parentheses/discuss/9478/No-stack-O(1)-space-complexity-O(n)-time-complexity-solution-in-C++/244061)
代码
代码支持：C++
C++:
1
class Solution {
2
public:
3
bool isValid(string s) {
4
int top = -1;
5
for(int i =0;i<s.length();++i){
6
if(top<0 || !isMatch(s[top], s[i])){
7
++top;
8
s[top] = s[i];
9
}else{
10
--top;
11
}
12
}
13
return top == -1;
14
}
15
bool isMatch(char c1, char c2){
16
if(c1 == '(' && c2 == ')') return true;
17
if(c1 == '[' && c2 == ']') return true;
18
if(c1 == '{' && c2 == '}') return true;
19
return false;
20
}
21
};
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
正则匹配
思路
我们不断通过消除 '[]' ， '()', '{}' ，最后判断剩下的是否是空串即可，就像开心消消乐一样。
代码
代码支持：Python，JavaScript
Python:
1
class Solution:
2
def isValid(self, s):
3
4
while '[]' in s or '()' in s or '{}' in s:
5
s = s.replace('[]','').replace('()','').replace('{}','')
6
return not len(s)
Copied!
JavaScript:
1
var isValid = function (s) {
2
while (s.includes("[]") || s.includes("()") || s.includes("{}")) {
3
s = s.replace("[]", "").replace("()", "").replace("{}", "");
4
}
5
s = s.replace("[]", "").replace("()", "").replace("{}", "");
6
return s.length === 0;
7
};
Copied!
复杂度分析
- 时间复杂度：取决于正则引擎的实现
- 空间复杂度：取决于正则引擎的实现
相关题目
扩展
- 如果让你检查 XML 标签是否闭合如何检查， 更进一步如果要你实现一个简单的 XML 的解析器，应该怎么实现？
- 事实上，这类问题还可以进一步扩展，我们可以去解析类似 HTML 等标记语法， 比如
<p></p> <body></body>
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago