20. Valid Parentheses

问题

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();
    }
};