问题
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.
例子
()[]{}
true
({[]})
true
([)]
false
分析
遍历字符串，用一个栈来保存( [ {这些open符号，遇到)]}这些close符号，就做如下判断：
- 栈为空，说明该字符串不是一个合法的字符串；
- 栈非空，弹出栈顶。如果栈顶元素和当前close符号匹配，则继续遍历字符串；否则说明该字符串不是一个合法的字符串。
要点
栈可以被用来计算表达式的值，也可以验证表达式的合法性。
时间复杂度
O(n)
空间复杂度
O(n)
代码
class Solution {
public:
bool isValid(string s) {
stack<char> es;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') es.push(c);
else {
if (es.empty()) return false;
if ((c == ')' && es.top() != '(') ||
(c == ']' && es.top() != '[') ||
(c == '}' && es.top() != '{'))
return false;
es.pop();
}
}
return es.empty();
}
};
