LeetCode20 Valid Parentheses

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

样例

1
2
Input:
"()"
1
2
Output:
true

思路

括号匹配问题。

用一个符号栈来维护即可。若当前的括号可以和栈顶括号匹配,则栈顶括号出栈,否则当前括号进栈,最后判断栈是否为空即可知道是否正确匹配完成。具体实现一般先在栈中压入一个特殊符号,避免栈为空的特判。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> hs;
hs[')'] = '('; hs['}'] = '{'; hs[']'] = '[';
stack<char> sta;
sta.push('#');
for (char&c : s) {
if (hs[c] != sta.top()) sta.push(c);
else sta.pop();
}
return sta.top() == '#';
}
};
分享到 评论