本文最后编辑于 前，其中的内容可能需要更新。
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
示例 2：
示例 3：
示例 4：
示例 5：
提示：
- $1 <= s.length <= 10^4$
s 仅由括号 '()[]{}' 组成
链接：
https://leetcode-cn.com/problems/valid-parentheses
题目分析
使用栈解决即可。遇到左括号入栈，遇到右括号判断当前栈顶元素是否是相匹配的括号，匹配则进行出栈，不匹配则直接返回 false。需要注意的是当栈为空时调用 top() 函数会出错，并且最后遍历完成之后若栈中还剩余有未匹配的左括号也说明结果为 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
bool isValid(string s) {
stack<char> par;
for(int i = 0; i < s.size(); i++){
if(s[i] == ')'){
if(par.empty() || par.top() != '(') return false;
else par.pop();
}
else if(s[i] == ']'){
if(par.empty() || par.top() != '[') return false;
else par.pop();
}
else if(s[i] == '}'){
if(par.empty() || par.top() != '{') return false;
else par.pop();
}
else{
par.push(s[i]);
}
}
return par.empty();
}
};
|
时间复杂度：$O(n)$，其中 $n$ 是括号串的长度。因为我们对该串进行了一次遍历。
空间复杂度：$O(n)$，其中 $n$ 是括号串的长度。我们维护了一个栈存放未匹配的括号，这个栈的最大大小为 $n$。
官方题解
官方题解也是同样用栈的思路，但是建立了一个哈希表进行匹配，代码显得漂亮一点。另外有一点是匹配的括号串一定是偶数个，如果括号串字符数为奇数则可以直接返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 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();
}
};
|