有效的括号 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

有效字符串需满足：

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

示例 1

输入：s = "()"

输出：true

示例 2

输入：s = "()[]{}"

输出：true

示例 3

输入：s = "(]"

输出：false

示例 4

输入：s = "([])"

输出：true

示例 5

输入：s = "([)]"

输出：false

💭 模拟答题者思考

1. 我先写暴力：对每个右括号，向前找最近一个未匹配的左括号，看类型是否一致——能判断，但要反复扫描、标记已用字符，实现又慢又乱。

2. 重复在哪里？每次匹配的都是「离当前右括号最近、且尚未闭合」的左括号——这正是后进先出（LIFO）的结构。

3. 用栈：遇左括号压栈；遇右括号看栈顶是否是与之配对的左括号，是则弹出，否则无效。扫完后栈空才有效。

4. 细节：右括号来时栈不能为空；类型必须严格匹配，(]、([)] 都会在匹配阶段失败。

5. 复杂度：每个字符最多入栈出栈各一次，时间 O(n)；最坏全是左括号时栈长 O(n)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`stk`	list / stack	定义：存放尚未被匹配的左括号维护：栈底到栈顶对应「从外到内、尚未闭合」的左括号序列更新：遇左括号 `push`；遇右括号且匹配成功则 `pop`，否则直接判无效
`pairs`	dict	定义：右括号到左括号的映射（`')'→'('` 等）维护：固定不变，覆盖三种括号对更新：无需更新，用 `pairs[c]` 查期望的栈顶左括号
`c`	char	定义：当前扫描到的字符维护：从左到右依次处理每个括号更新：每轮循环取下一个字符，按左/右分支更新栈或提前返回 `False`

⌨️ 落码步骤

1. 建立右→左括号映射 pairs = {')':'(', ']':'[', '}':'{'}

2. 初始化空栈 stk = []，从左到右遍历每个字符 c

3. 若 c 是左括号（不在 pairs 的 key 中），stk.append(c)

4. 若 c 是右括号：栈空或 stk[-1] != pairs[c] 则返回 False，否则 stk.pop()

5. 遍历结束，返回 len(stk) == 0

💻 代码实现

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {')': '(', ']': '[', '}': '{'}
        stk = []
        for c in s:
            if c not in pairs:          # 左括号，等待匹配
                stk.append(c)
            elif not stk or stk[-1] != pairs[c]:  # 右括号无法配对
                return False
            else:
                stk.pop()
        return not stk

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> pairs = {
            {')', '('}, {']', '['}, {'}', '{'}
        };
        vector<char> stk;
        for (char c : s) {
            if (!pairs.count(c)) {       // 左括号，等待匹配
                stk.push_back(c);
            } else if (stk.empty() || stk.back() != pairs[c]) {
                return false;            // 右括号无法配对
            } else {
                stk.pop_back();
            }
        }
        return stk.empty();
    }
};
// 时间 O(n)，空间 O(n)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)

⚠️ 常见坑

❗ 右括号来时忘记检查栈空：如 ")"、"]" 会直接访问空栈顶导致错误。

❗ 只判断「栈非空」不判断类型：(] 栈顶是 ( 却遇到 ]，必须返回 False。

❗ 遍历结束后忘记检查栈是否为空："("、"([(" 等左括号未闭合应判无效。

🔍 必测边界 Case

Case 1：单个左括号未闭合

s = "(" → false

Case 2：单个右括号无匹配

s = ")" → false

Case 3：嵌套与交叉

s = "([])" → true；s = "([)]" → false