有效的括号 - LonelyStar

题目链接：20. 有效的括号 - 力扣（LeetCode）

难度：简单
标签：栈、字符串

题目描述#

Note

原题说明：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例#

输入：s = "()[]{}" -> 输出：true
输入：s = "(]" -> 输出：false
输入：s = "([])" -> 输出：true

方案一：错误的“回文”尝试#

最初看到题目时，我产生了一个很“骚”的想法：既然括号是对称的，那是不是可以用判断回文数的逻辑来做？

我的第一版尝试（失败经验）#

1
class Solution {
2
public:
3
    bool isValid(string s) {
4
        if(s.empty()) return false;
5
        string str = s.substr(s.length()/2, s.length());
6
        string str2 = s.substr(0, s.length()/2);
7
        reverse(str.begin(), str.end());
8
        return str == str2;
9
    }
10
};

为什么行不通？

嵌套问题：([]) 是有效的，但它不是简单的翻转关系。
符号差异：括号不是数字，反转后还需要对应的方向转换（如 [ 变 ]）。
顺序非单一性：括号可以是一对接一对的 ()[]{}，也可以是嵌套的 ({[]})，回文逻辑只能覆盖一部分极简情况。

方案二：栈（Stack）的经典应用（推荐）#

括号匹配是**栈（Stack）**数据结构的教科书级应用。栈具有 后进先出 (LIFO) 的特性，这完美契合了“最后进去的左括号必须最先被抵消”的原则。

源码实现#

1
#include <stack>
2
#include <string>
3
using namespace std;
4

5
class Solution {
6
public:
7
    bool isValid(string s) {
8
        stack<char> st;
9

10
        for (char c : s) {
11
            // 如果是左括号，直接入栈
12
            if (c == '(' || c == '[' || c == '{') {
13
                st.push(c);
14
            }
15
            // 如果是右括号，检查栈顶是否匹配
16
            else {
17
                if (st.empty()) return false; // 栈为空却收到了右括号，无效
18

19
                char top = st.top();
20
                st.pop();
21

22
                if ((c == ')' && top != '(') ||
23
                    (c == ']' && top != '[') ||
24
                    (c == '}' && top != '{')) {
25
                    return false;
26
                }
27
            }
28
        }
29
        // 最后必须保证栈内所有左括号都被抵消了
30
        return st.empty();
31
    }
32
};

复杂度分析#

时间复杂度： $O(n)$ 。我们只需遍历一次包含 $n$ 个字符的字符串，每个字符最多入栈一次、出栈一次。
空间复杂度： $O(n)$ 。在最坏情况下（所有字符都是左括号），栈的深度会达到 $n$ 。

总结#

理解栈的本质：栈是处理具有“对称性”或“后效性”问题的神器。在这个题目中，每一个右括号都在寻找它之前的“邻居”左括号。
边界条件：
- 字符串为空的情况。
- 只有右括号的情况（如 ))}）。
- 只有左括号的情况（如 (([）。

Tip

以后碰到这种“成对出现”、“最近匹配”或“消除”类的问题，第一个就要想到栈！

音乐

音乐