LeetCode 第 301 题“删除无效的括号”
字数 2883 2025-10-26 10:19:10

好的，我们接下来讲解 LeetCode 第 301 题“删除无效的括号”。

题目描述

给你一个由若干括号和字母组成的字符串 s，删除最少数量的无效括号，使得括号匹配有效。返回所有可能的结果（任意顺序返回）。

示例 1
输入：s = "()())()"
输出：["(())()","()()()"]

示例 2
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3
输入：s = ")("
输出：[""]

说明

  • 1 <= s.length <= 25
  • s 由小写英文字母以及括号 '(' 和 ')' 组成
  • 可能含有多个有效结果

解题思路

第一步：理解问题核心

  1. 括号匹配规则

    • 左括号 '(' 必须与右括号 ')' 匹配。
    • 匹配过程中，任意前缀中左括号数量不能少于右括号数量。
    • 最终左右括号数量相等。

  2. 无效括号

    • 多余的 '(' 或 ')' 需要删除。
    • 删除的数量要最少，即去掉最少的括号使括号匹配。

  3. 输出所有可能结果

    • 可能有多个删除方案得到不同的有效字符串。
    • 要去重，因为不同删除位置可能得到相同字符串。

第二步：计算最少应删除几个左括号、几个右括号

我们遍历一次字符串，用一个计数方法判断有多少括号不匹配：

  • 设 leftCount 为当前多余的左括号（还未匹配的）。
  • 设 rightCount 为当前需要删除的右括号（出现在多余左括号之前的多余右括号）。

遍历逻辑：

  1. 遇到 '('：leftCount++
  2. 遇到 ')'：
    • 如果 leftCount > 0，说明有左括号可以匹配它，则 leftCount--
    • 否则这个右括号是多余的，rightCount++

遍历结束后，leftCount 就是多余的左括号数量，rightCount 是多余的右括号数量。
最少删除数量 = leftCount + rightCount。

第三步：暴力回溯思路

我们可以用 DFS（回溯）尝试删除某些括号：

  • 从字符串第一个字符开始，对每个括号字符尝试“删除”或“保留”。
  • 如果删除了超过应删除的数量，剪枝。
  • 最终检查字符串是否有效。

但直接枚举每个括号删或不删，复杂度 O(2^n)，n ≤ 25 时可能较大（2^25 ≈ 3.3 千万），但题目数据范围允许勉强通过，不过需要优化。

第四步：优化回溯

我们已知应删除的左右括号数量：lRemove 和 rRemove。

回溯参数：

  • index：当前处理到字符串的位置
  • lCount：当前已使用的左括号数量（已加入结果字符串的）
  • rCount：当前已使用的右括号数量
  • lRemove：还可以删除的左括号数量
  • rRemove：还可以删除的右括号数量
  • path：当前已选择的字符组成的字符串

剪枝：

  1. 如果 lCount < rCount，当前路径已经无效（右括号多于左括号），直接返回。
  2. 如果 lRemove 或 rRemove 小于 0，说明删多了，返回。
  3. 如果剩余字符数不够组成有效字符串（剩余字符数 < 还需要匹配的括号数），剪枝（可选优化）。

当处理完整个字符串：

  • 如果 lRemove == 0 且 rRemove == 0，检查 path 是否有效（其实剪枝保证了最终一定有效，但可以再验证一次）。
  • 有效则加入结果集。

第五步：去重与避免重复删除

字符串中可能有连续相同括号，比如 "())"，在删除右括号时，删除第一个 ')' 和删除第二个 ')' 结果一样。
为避免重复结果，当遇到连续相同括号时，只尝试删除第一个，跳过后面相同的（即“在当前层，对于相同字符只删除一次”）。

具体：

  • 在回溯的每一层，记录当前层已尝试删除的字符，如果相同字符已经尝试删除过，则跳过。

第六步：回溯算法步骤

  1. 先计算 lRemove 和 rRemove（多余括号数）。
  2. 回溯函数 backtrack(index, lCount, rCount, lRemove, rRemove, path)：
    • 如果 index == len(s)：
      • 如果 lRemove == 0 and rRemove == 0 且 lCount == rCount，将 path 加入结果。
      • 返回
    • 当前字符 ch = s[index]
    • 情况1：删除当前字符（如果是括号）：
      • 如果是 '(' 且 lRemove > 0，则递归：backtrack(index+1, lCount, rCount, lRemove-1, rRemove, path)
      • 如果是 ')' 且 rRemove > 0，则递归：backtrack(index+1, lCount, rCount, lRemove, rRemove-1, path)
    • 情况2：保留当前字符：
      • 如果是字母，直接加入，递归下一位置。
      • 如果是 '('：backtrack(index+1, lCount+1, rCount, lRemove, rRemove, path + '(')
      • 如果是 ')'：只有 lCount > rCount 时才可保留（保证不破坏有效性），然后 rCount+1 递归。
    • 注意在每一层用集合记录已尝试删除的字符，避免重复。
  3. 起始调用：backtrack(0, 0, 0, lRemove, rRemove, "")
  4. 返回结果列表。

第七步：示例演示

以 s = "()())()" 为例：

  1. 计算 lRemove, rRemove：

    • 遍历：
      i=0: '(' → leftCount=1
      i=1: ')' → leftCount=0
      i=2: '(' → leftCount=1
      i=3: ')' → leftCount=0
      i=4: ')' → 此时 leftCount=0，所以 rightCount=1（多余右括号）
      i=5: '(' → leftCount=1
      i=6: ')' → leftCount=0
      结束：lRemove=0, rRemove=1。

  2. 回溯尝试删除 1 个右括号（位置需尝试）：

    • 删除索引 4 的 ')' 得到 "(())()"
    • 删除索引 3 的 ')' 得到 "()()()"
    • 其他删除位置会重复或无效。

结果：["(())()","()()()"]

第八步：复杂度分析

  • 最坏情况：字符串全是括号，应删除数约 n/2，但剪枝和去重优化后实际运行较快。
  • 时间复杂度：O(2^n) 理论上界，但剪枝后远小于。
  • 空间复杂度：O(n^2) 因为递归深度 n 且每层可能存字符串。

核心要点总结

  1. 先计算最少需删除的左右括号数。
  2. 回溯时跟踪当前左右括号数量，确保不破坏有效性。
  3. 遇到连续相同括号时，只删除第一个以避免重复。
  4. 最终验证字符串有效（可省略，因剪枝已保证）。

这样就能高效求出所有可能结果。

好的，我们接下来讲解 LeetCode 第 301 题“删除无效的括号” 。 题目描述 给你一个由若干括号和字母组成的字符串 s ，删除最少数量的无效括号，使得括号匹配有效。返回所有可能的结果（任意顺序返回）。 示例 1 输入：s = "()())()" 输出：[ "(())()","()()()" ] 示例 2 输入：s = "(a)())()" 输出：[ "(a())()","(a)()()" ] 示例 3 输入：s = ")(" 输出：[ "" ] 说明 1 <= s.length <= 25 s 由小写英文字母以及括号 '(' 和 ')' 组成 可能含有多个有效结果 解题思路 第一步：理解问题核心 括号匹配规则 左括号 '(' 必须与右括号 ')' 匹配。 匹配过程中，任意前缀中左括号数量不能少于右括号数量。 最终左右括号数量相等。 无效括号 多余的 '(' 或 ')' 需要删除。 删除的数量要最少，即去掉最少的括号使括号匹配。 输出所有可能结果 可能有多个删除方案得到不同的有效字符串。 要去重，因为不同删除位置可能得到相同字符串。 第二步：计算最少应删除几个左括号、几个右括号 我们遍历一次字符串，用一个计数方法判断有多少括号不匹配： 设 leftCount 为当前多余的左括号（还未匹配的）。 设 rightCount 为当前需要删除的右括号（出现在多余左括号之前的多余右括号）。 遍历逻辑： 遇到 '(' ： leftCount++ 遇到 ')' ： 如果 leftCount > 0 ，说明有左括号可以匹配它，则 leftCount-- 否则这个右括号是多余的， rightCount++ 遍历结束后， leftCount 就是多余的左括号数量， rightCount 是多余的右括号数量。 最少删除数量 = leftCount + rightCount 。 第三步：暴力回溯思路 我们可以用 DFS（回溯）尝试删除某些括号： 从字符串第一个字符开始，对每个括号字符尝试“删除”或“保留”。 如果删除了超过应删除的数量，剪枝。 最终检查字符串是否有效。 但直接枚举每个括号删或不删，复杂度 O(2^n)，n ≤ 25 时可能较大（2^25 ≈ 3.3 千万），但题目数据范围允许勉强通过，不过需要优化。 第四步：优化回溯 我们已知应删除的左右括号数量： lRemove 和 rRemove 。 回溯参数： index ：当前处理到字符串的位置 lCount ：当前已使用的左括号数量（已加入结果字符串的） rCount ：当前已使用的右括号数量 lRemove ：还可以删除的左括号数量 rRemove ：还可以删除的右括号数量 path ：当前已选择的字符组成的字符串 剪枝： 如果 lCount < rCount ，当前路径已经无效（右括号多于左括号），直接返回。 如果 lRemove 或 rRemove 小于 0，说明删多了，返回。 如果剩余字符数不够组成有效字符串（剩余字符数 < 还需要匹配的括号数），剪枝（可选优化）。 当处理完整个字符串： 如果 lRemove == 0 且 rRemove == 0 ，检查 path 是否有效（其实剪枝保证了最终一定有效，但可以再验证一次）。 有效则加入结果集。 第五步：去重与避免重复删除 字符串中可能有连续相同括号，比如 "())" ，在删除右括号时，删除第一个 ')' 和删除第二个 ')' 结果一样。 为避免重复结果，当遇到连续相同括号时，只尝试删除第一个，跳过后面相同的（即“在当前层，对于相同字符只删除一次”）。 具体： 在回溯的每一层，记录当前层已尝试删除的字符，如果相同字符已经尝试删除过，则跳过。 第六步：回溯算法步骤 先计算 lRemove 和 rRemove （多余括号数）。 回溯函数 backtrack(index, lCount, rCount, lRemove, rRemove, path) ： 如果 index == len(s) ： 如果 lRemove == 0 and rRemove == 0 且 lCount == rCount ，将 path 加入结果。 返回 当前字符 ch = s[index] 情况1：删除当前字符（如果是括号）： 如果是 '(' 且 lRemove > 0 ，则递归： backtrack(index+1, lCount, rCount, lRemove-1, rRemove, path) 如果是 ')' 且 rRemove > 0 ，则递归： backtrack(index+1, lCount, rCount, lRemove, rRemove-1, path) 情况2：保留当前字符： 如果是字母，直接加入，递归下一位置。 如果是 '(' ： backtrack(index+1, lCount+1, rCount, lRemove, rRemove, path + '(') 如果是 ')' ：只有 lCount > rCount 时才可保留（保证不破坏有效性），然后 rCount+1 递归。 注意在每一层用集合记录已尝试删除的字符，避免重复。 起始调用： backtrack(0, 0, 0, lRemove, rRemove, "") 返回结果列表。 第七步：示例演示 以 s = "()())()" 为例： 计算 lRemove , rRemove ： 遍历： i=0: '(' → leftCount=1 i=1: ')' → leftCount=0 i=2: '(' → leftCount=1 i=3: ')' → leftCount=0 i=4: ')' → 此时 leftCount=0，所以 rightCount=1（多余右括号） i=5: '(' → leftCount=1 i=6: ')' → leftCount=0 结束：lRemove=0, rRemove=1。 回溯尝试删除 1 个右括号（位置需尝试）： 删除索引 4 的 ')' 得到 "(())()" 删除索引 3 的 ')' 得到 "()()()" 其他删除位置会重复或无效。 结果： ["(())()","()()()"] 第八步：复杂度分析 最坏情况：字符串全是括号，应删除数约 n/2，但剪枝和去重优化后实际运行较快。 时间复杂度：O(2^n) 理论上界，但剪枝后远小于。 空间复杂度：O(n^2) 因为递归深度 n 且每层可能存字符串。 核心要点总结 先计算最少需删除的左右括号数。 回溯时跟踪当前左右括号数量，确保不破坏有效性。 遇到连续相同括号时，只删除第一个以避免重复。 最终验证字符串有效（可省略，因剪枝已保证）。 这样就能高效求出所有可能结果。