题目描述

给定一个嵌套的括号序列，含有 ( ) [ ] { } 三种括号，判断序列是否合法。

样例

"()" 和 "()[]{}" 是合法的；
"(]" 和 "([)]" 不是合法的。

算法

(栈结构) $O(n)$

使用栈数据结构：

1. 遇到左括号，需要压栈。
2. 遇到右括号，判断栈顶是否和当前右括号匹配；若不匹配则返回false，否则匹配弹出栈顶。
3. 最后判断栈是否为空；若为空则合法，否则不合法。

时间复杂度

• 只需要遍历一次整个序列，所以是 $O(n)$ 的。

空间复杂度

• 栈需要 $O(n)$ 的空间。

C++ 代码

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
                stk.push(s[i]);
            else if (s[i] == ')') {
                if (stk.empty() || stk.top() != '(')
                    return false;
                stk.pop();
            }
            else if (s[i] == ']') {
                if (stk.empty() || stk.top() != '[')
                    return false;
                stk.pop();
            }
            else {
                if (stk.empty() || stk.top() != '{')
                    return false;
                stk.pop();
            }
        }
        return stk.empty();
    }
};