跳到主要内容

20. 有效的括号

题目描述​

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

有效字符串需满足：

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

示例：

  • 输入：s = "()" → 输出：true
  • 输入：s = "()[]{}" → 输出：true
  • 输入：s = "(]" → 输出：false
  • 输入：s = "([)]" → 输出：false
  • 输入：s = "{[]}" → 输出：true

解题思路​

第一步：理解问题本质​

括号匹配有一个关键性质：最近遇到的未闭合左括号，必须最先被闭合。

用一个具体的例子来说明：{[()]}

  • 遇到 {，它等待被 } 闭合。
  • 遇到 [，它比 { 更晚出现，必须先于 { 被闭合。
  • 遇到 (，它比 [ 更晚出现，必须先于 [ 被闭合。
  • 遇到 )，正好闭合最近的 (，合法。
  • 遇到 ]，正好闭合最近的 [，合法。
  • 遇到 }，正好闭合最近的 {，合法。

这种"后进先出"的结构，正是栈的天然应用场景。

第二步：暴力解法​

反复扫描字符串，每次找到相邻的合法括号对（如 ()、[]、{}）并删除，直到字符串为空（合法）或无法继续删除（非法）。

class Solution:
    def isValid(self, s: str) -> bool:
        while "()" in s or "[]" in s or "{}" in s:
            s = s.replace("()", "").replace("[]", "").replace("{}", "")
        return s == ""

时间复杂度：O(n²)，每次替换最多删除一对，最多做 n/2 次，每次字符串操作 O(n)。

为何不够好：字符串替换操作开销大，而且每轮只能处理最内层的括号对，效率低。使用栈可以一次遍历完成，达到 O(n)。

第三步：最优解法（栈）​

核心思路：

  • 遇到左括号（(、[、{）：将其压入栈，等待对应的右括号来闭合它。
  • 遇到右括号（)、]、}）：检查栈顶是否是对应的左括号。
    • 若栈为空：没有待匹配的左括号，非法，返回 False。
    • 若栈顶不匹配：类型不对应，非法，返回 False。
    • 若栈顶匹配：弹出栈顶，继续处理下一个字符。
  • 遍历结束后：若栈为空，说明所有左括号都已被正确闭合，返回 True；若栈非空，说明有未闭合的左括号，返回 False。

哈希表的作用：用 pair_map = {')': '(', ']': '[', '}': '{'} 将每个右括号映射到其对应的左括号，使得匹配判断只需一行代码，避免三个 if-else 分支。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pair_map = {')': '(', ']': '[', '}': '{'}
        for char in s:
            if char in '([{':
                stack.append(char)
            else:
                if not stack or stack.pop() != pair_map[char]:
                    return False
        return len(stack) == 0

完整代码实现​

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pair_map = {')': '(', ']': '[', '}': '{'}
        for char in s:
            if char in '([{':          # 左括号，压栈
                stack.append(char)
            else:                       # 右括号，检查栈顶
                if not stack or stack.pop() != pair_map[char]:
                    return False        # 栈空或类型不匹配
        return len(stack) == 0          # 栈为空才说明全部合法闭合

示例推演​

以 s = "({[]})" 为例，期望输出 True。

步骤字符操作栈状态（栈底→栈顶）
1(左括号，压栈['(']
2{左括号，压栈['(', '{']
3[左括号，压栈['(', '{', '[']
4]右括号，pair_map[']']='['，弹出栈顶 '['，匹配['(', '{']
5}右括号，pair_map['}']='{'，弹出栈顶 '{'，匹配['(']
6)右括号，pair_map[')']='('，弹出栈顶 '('，匹配[]

遍历结束，栈为空，返回 True。

再以 s = "([)]" 为例，期望输出 False。

步骤字符操作栈状态
1(压栈['(']
2[压栈['(', '[']
3)pair_map[')']='('，弹出栈顶 '['，'[' != '('，不匹配！—

立刻返回 False，正确。

复杂度分析​

解法时间复杂度空间复杂度说明
暴力（反复替换）O(n²)O(n)每轮替换 O(n)，最多 n/2 轮
最优（栈）O(n)O(n)每个字符最多入栈出栈各一次

栈的空间最坏情况下（全是左括号时）存储 n 个元素，空间复杂度为 O(n)。

易错点总结​

  1. 先判断栈空再弹出：遇到右括号时，必须先检查 not stack，再执行 stack.pop()。若先 pop 后比较，空栈会抛出 IndexError。代码中用 not stack or stack.pop() != pair_map[char] 利用短路求值，not stack 为真时不会执行后面的 pop。
  2. 遍历结束后必须检查栈是否为空：即使遍历中没有触发 return False，也可能存在未闭合的左括号留在栈中（如 s = "((" 这种情况），必须用 return len(stack) == 0 来最终判断。
  3. 奇数长度字符串必然非法：可以在开头加 if len(s) % 2 == 1: return False 提前剪枝，但题目约束下非必须。

扩展思考​

  • 括号生成（LeetCode 22）：反向问题，给定 n 对括号，生成所有合法组合，同样用栈（或递归）的思路来确保括号合法性。
  • 最长有效括号（LeetCode 32）：在括号序列中找最长的合法子串，也是栈的经典应用，难度升级为困难。
  • 栈的本质：栈处理的是"对称嵌套"结构——任何具有"后出现的需要先结束"特性的问题，都是栈的适用场景。括号匹配是最典型的例子，其他如函数调用栈、HTML 标签匹配等都遵循相同原理。
加载评论中...