算法 - 有效的括号 (Valid Parentheses)

Posted on

1. 题目

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

有效字符串需满足：

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

示例:

1
2
3
4
5
"()"        -> true
"()[]{}"    -> true
"(]"        -> false
"([)]"      -> false
"{[]}"      -> true

2. 解题思路

括号匹配是栈的招牌应用场景。核心规律：最近打开的括号，必须最先被闭合（后进先出）。

遍历字符串：

  • 遇到左括号，压栈。
  • 遇到右括号，看栈顶：
    • 栈为空 → 没有可匹配的左括号，false。
    • 栈顶不是对应的左括号 → 顺序或类型错误，false。
    • 匹配成功 → 弹出栈顶。
  • 全部遍历结束后，栈必须为空（所有左括号都被闭合），否则 false。

一个常见优化技巧：遇到右括号时，如果它应该匹配的左括号不在栈顶，立即失败，无需额外判断。

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)，最坏全是左括号。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function isValid(s: string): boolean {
    const pairs: Record<string, string> = {
        ')': '(',
        ']': '[',
        '}': '{',
    };
    const stack: string[] = [];

    for (const ch of s) {
        // 右括号：栈顶必须是对应的左括号
        if (ch in pairs) {
            const top = stack.pop(); // 空数组 pop 返回 undefined，天然处理空栈
            if (top !== pairs[ch]) return false;
        } else {
            // 左括号：入栈
            stack.push(ch);
        }
    }

    return stack.length === 0;
}

// 测试
console.log(isValid("{[]}")); // true
console.log(isValid("([)]")); // false
console.log(isValid("("));    // false

4. 面试延伸

  • 最长有效括号（LeetCode 32） 用栈记录下标，求长度；进阶可用 DP，是难题级别。
  • 括号生成（22 题） 是回溯：维护左右括号计数，left < n 加左括号、right < left 加右括号。
  • 有效括号 III / 通配符（1047 删重复） 等都用栈，掌握「遇右查栈顶」这一招就能举一反三。
  • 扩展字符集（如标签嵌套 <div>）时，把 Record 换成 Map 支持多字符 key 即可。

难度：简单 | LeetCode 20 题 | 栈应用第一课