题目链接 · 灵神原题解（署名来源）

题意解读

什么情况下是有效字符串？

可以从消消乐的角度理解，每次可以消除一对相邻的匹配括号，不断消除，如果可以把 $s$ 变成空字符串，则 $s$ 是有效字符串。

比如 $\mathtt{\text{()}},\mathtt{\text{(())}},\mathtt{\text{[()]}},\mathtt{\text{[()]{}}}$ 等等，都可以通过消除，把 $s$ 变成空字符串。例如

$$\mathtt{\text{[()]}}\to \mathtt{\text{[]}}\to \mathrm{空}\mathrm{串}$$

什么情况下是无效字符串？

1. 左括号没有对应的右括号。例如 $\mathtt{\text{(()}}$，缺失了一个右括号。
2. 右括号没有对应的左括号。例如 $\mathtt{\text{())}}$，缺失了一个左括号。
3. 括号类型不匹配。例如 $\mathtt{\text{[()}}}$，其中 $\mathtt{\text{[}}$ 要和 $\mathtt{\text{}}}$ 组成一对括号，但是括号类型不同。

思路

本题是「邻项消除」问题（见文末的题单），这类问题都可以用栈解决。

以 $s=\mathtt{\text{{[()]}}}$ 为例说明：

1. 创建一个空栈。
2. 从左到右遍历 $s$。
3. $s[0]=\mathtt{\text{{}}$，这是一个左括号，入栈。
4. $s[1]=\mathtt{\text{[}}$，这是一个左括号，入栈。
5. $s[2]=\mathtt{\text{(}}$，这是一个左括号，入栈。
6. $s[3]=\mathtt{\text{)}}$，这是一个右括号，它必须和栈顶的 $\mathtt{\text{(}}$ 组成一对（消除），弹出栈顶。
7. $s[4]=\mathtt{\text{]}}$，这是一个右括号，它必须和栈顶的 $\mathtt{\text{[}}$ 组成一对（消除），弹出栈顶。
8. $s[5]=\mathtt{\text{}}}$，这是一个右括号，它必须和栈顶的 $\mathtt{\text{{}}$ 组成一对（消除），弹出栈顶。
9. 遍历结束，由于栈为空，说明所有括号均已匹配完毕，返回 $\mathtt{\text{true}}$。反之，如果在遍历的过程中，发现栈为空，或者括号类型不匹配的情况，返回 $\mathtt{\text{false}}$。此外，如果遍历结束栈不为空，说明还有没匹配的左括号，返回 $\mathtt{\text{false}}$。

细节

1. 由于括号两两一对，所以 $s$ 的长度必须是偶数。如果 $s$ 的长度是奇数，可以直接返回 $\mathtt{\text{false}}$。
2. 我们可以创建一个哈希表（或者数组），保存每个右括号对应的左括号，这样可以直接判断栈顶的左括号是否与右括号为同一类型，从而省去大量 if-else 判断。

写法一

Python 解法1

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2:  # s 长度必须是偶数
            return False
        mp = {')': '(', ']': '[', '}': '{'}
        st = []
        for c in s:
            if c not in mp:  # c 是左括号
                st.append(c)  # 入栈
            elif not st or st.pop() != mp[c]:  # c 是右括号
                return False  # 没有左括号，或者左括号类型不对
        return not st  # 所有左括号必须匹配完毕

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
    unordered_map<char, char> mp = {{')', '('}, {']', '['}, {'}', '{'}};
public:
    bool isValid(string s) {
        if (s.length() % 2) { // s 长度必须是偶数
            return false;
        }
        stack<char> st;
        for (char c : s) {
            // mp.contains(c) 用来判断 c 是不是 mp 的一个 key
            if (!mp.contains(c)) { // c 是左括号
                st.push(c); // 入栈
            } else { // c 是右括号
                if (st.empty() || st.top() != mp[c]) {
                    return false; // 没有左括号，或者左括号类型不对
                }
                st.pop(); // 出栈
            }
        }
        return st.empty(); // 所有左括号必须匹配完毕
    }
};

写法二

也可以在哈希表/数组中保存每个左括号对应的右括号。在遍历到左括号时，把对应的右括号入栈。这样遍历到右括号时，只需看栈顶括号是否一样即可。

Python 解法3

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2:  # s 长度必须是偶数
            return False
        mp = {'(': ')', '[': ']', '{': '}'}
        st = []
        for c in s:
            if c in mp:  # c 是左括号
                st.append(mp[c])  # 入栈对应的右括号
            elif not st or st.pop() != c:  # c 是右括号
                return False  # 没有左括号，或者左括号类型不对
        return not st  # 所有左括号必须匹配完毕

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
    unordered_map<char, char> mp = {{'(', ')'}, {'[', ']'}, {'{', '}'}};
public:
    bool isValid(string s) {
        if (s.length() % 2) { // s 长度必须是偶数
            return false;
        }
        stack<char> st;
        for (char c : s) {
            if (mp.contains(c)) { // c 是左括号
                st.push(mp[c]); // 入栈对应的右括号
            } else { // c 是右括号
                if (st.empty() || st.top() != c) {
                    return false; // 没有左括号，或者左括号类型不对
                }
                st.pop(); // 出栈
            }
        }
        return st.empty(); // 所有左括号必须匹配完毕
    }
};

写法三

用 if-else 代替 mp。

Python 解法5

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2:  # s 长度必须是偶数
            return False
        st = []
        for c in s:
            if c == '(':
                st.append(')')  # 入栈对应的右括号
            elif c == '[':
                st.append(']')
            elif c == '{':
                st.append('}')
            elif not st or st.pop() != c:  # c 是右括号
                return False  # 没有左括号，或者左括号类型不对
        return not st  # 所有左括号必须匹配完毕

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    bool isValid(string s) {
        if (s.length() % 2) { // s 长度必须是偶数
            return false;
        }
        stack<char> st;
        for (char c : s) {
            if (c == '(') {
                st.push(')'); // 入栈对应的右括号
            } else if (c == '[') {
                st.push(']');
            } else if (c == '{') {
                st.push('}');
            } else { // c 是右括号
                if (st.empty() || st.top() != c) {
                    return false; // 没有左括号，或者左括号类型不对
                }
                st.pop(); // 出栈
            }
        }
        return st.empty(); // 所有左括号必须匹配完毕
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$ 或 $\mathcal{O}(1)$。如果能修改 $s$，那么直接把 $s$ 当作栈，可以做到 $\mathcal{O}(1)$ 额外空间。

相似题目

见 数据结构题单 中的【§3.3 邻项消除】。

分类题单

如何科学刷题？

1. 滑动窗口（定长/不定长/多指针）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心算法（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府