301. 删除无效的括号

题目链接（困难）

题目描述

给你一个由若干括号和字母组成的字符串 s，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

数据范围：

• 1 <= s.length <= 25
• s 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

示例

示例 1：

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

示例 2：

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

示例 3：

输入： s = ")("
输出： [""]

核心思路

题目要求删除最少数量的无效括号，并返回所有可能的结果。

第一步：统计最少需要删除的左括号数 left_rem 和右括号数 right_rem。

扫描一遍字符串，用 left 记录未匹配的 (，用 right 记录未匹配的 )：

• 遇到 (：left += 1；
• 遇到 )：
  • 若 left > 0：可以和前面的 ( 匹配，left -= 1；
  • 否则：这个 ) 多余，right += 1。

扫描结束后，left 就是需要删除的多余左括号数量，right 就是需要删除的多余右括号数量。

第二步：枚举每个字符「删除」或「保留」。

因为最多只有 20 个括号，可以用 DFS 枚举所有可能的删除方案，并加上剪枝：

• 删除的左右括号数量不能超过 left_rem / right_rem；
• 保留 ) 时，必须保证当前 balance > 0（即前面有未匹配的 (），否则字符串非法；
• 到达末尾时，要求 left_rem == 0、right_rem == 0 且 balance == 0。

用 set 去重，避免因删除不同位置的相同括号而产生重复结果。

---

方法一：DFS + 剪枝（按字符选择）✅ 推荐

思路及解法

从前往后遍历字符串，对每个字符做「删除」或「保留」的决策：

• 如果是 (：
  • 可以删除它（前提 l_rem > 0）；
  • 也可以保留它（balance += 1）。
• 如果是 )：
  • 可以删除它（前提 r_rem > 0）；
  • 也可以保留它（前提 balance > 0，否则会出现负平衡，非法）。
• 如果是字母：直接保留。

当遍历到末尾时，如果满足：

• l_rem == 0
• r_rem == 0
• balance == 0

说明删除了恰好所需数量的括号，且字符串合法，加入结果集。

为什么用 set 去重：删除不同位置的相同括号可能得到相同的字符串，用集合自动去重。

代码

from typing import List

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 1. 计算最少需要删除的左右括号数量
        left_rem = 0
        right_rem = 0
        for ch in s:
            if ch == '(':
                left_rem += 1
            elif ch == ')':
                if left_rem > 0:
                    left_rem -= 1
                else:
                    right_rem += 1

        res = set()

        # 2. DFS 枚举删除/保留
        def dfs(i, l_rem, r_rem, balance, path):
            if i == len(s):
                if l_rem == 0 and r_rem == 0 and balance == 0:
                    res.add(''.join(path))
                return

            ch = s[i]
            if ch == '(':
                # 删除当前 '('
                if l_rem > 0:
                    dfs(i + 1, l_rem - 1, r_rem, balance, path)
                # 保留当前 '('
                path.append(ch)
                dfs(i + 1, l_rem, r_rem, balance + 1, path)
                path.pop()
            elif ch == ')':
                # 删除当前 ')'
                if r_rem > 0:
                    dfs(i + 1, l_rem, r_rem - 1, balance, path)
                # 保留当前 ')'，前提是 balance > 0
                if balance > 0:
                    path.append(ch)
                    dfs(i + 1, l_rem, r_rem, balance - 1, path)
                    path.pop()
            else:
                # 字母直接保留
                path.append(ch)
                dfs(i + 1, l_rem, r_rem, balance, path)
                path.pop()

        dfs(0, left_rem, right_rem, 0, [])
        return list(res)

复杂度分析

• 时间复杂度：最坏情况下 $O(2^m \cdot n)$，其中 $m$ 是括号数量（最多 20），$n$ 是字符串长度。实际由于剪枝，运行很快。
• 空间复杂度：$O(n)$，递归栈深度和临时路径长度。

---

方法二：BFS（广度优先搜索）

思路及解法

核心思想：最少删除问题天然适合 BFS。

• 从原字符串出发；
• 每轮对上一层所有字符串，尝试删除一个括号，得到新字符串，去重后作为下一层；
• 检查每层中的字符串是否合法，若合法，把该层所有合法的加入答案，然后立即结束。

为什么可以立即结束：

• BFS 层数就是删除次数；
• 第一次出现合法字符串的层数，就是最少删除次数；
• 所以找到后返回即可。

用 set 去重：同一层可能出现重复字符串，用集合去重能大幅减少工作量。

代码

class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        def is_valid(string: str) -> bool:
            cnt = 0
            for c in string:
                if c == '(':
                    cnt += 1
                elif c == ')':
                    cnt -= 1
                    if cnt < 0:
                        return False
            return cnt == 0

        ans = []
        curr_set = {s}

        while True:
            # 检查当前层的所有字符串
            for string in curr_set:
                if is_valid(string):
                    ans.append(string)

            # 本层已有合法字符串，直接返回
            if ans:
                return ans

            # 构造下一层
            next_set = set()
            for string in curr_set:
                for i in range(len(string)):
                    # 跳过连续相同的括号
                    if i > 0 and string[i] == string[i - 1]:
                        continue
                    if string[i] == '(' or string[i] == ')':
                        next_set.add(string[:i] + string[i + 1:])
            curr_set = next_set

        return ans

复杂度分析

• 时间复杂度：$O(n \cdot 2^n)$，每层枚举删除位置。
• 空间复杂度：$O(n \cdot C_n^{n/2})$，最坏情况下队列中存大量字符串。

---

两种方法对比

方法	时间	空间	特点
DFS + 剪枝	$O(2^m \cdot n)$	$O(n)$	精确知道要删几个，剪枝充分，代码简洁
BFS	$O(n \cdot 2^n)$	$O(n \cdot C_n^{n/2})$	层数即删除数，思路自然，但可能存储较多中间结果

推荐：

• 面试：首选 DFS + 剪枝，因为有 left_rem / right_rem 的精确控制，搜索空间更小，代码也短；
• 理解最少删除：BFS 更直观，因为「层数 = 删除次数」。

---

关键细节

1. 预处理 left_rem / right_rem 的正确性

扫描规则：

• 遇到 (：left_rem += 1；
• 遇到 )：
  • 若 left_rem > 0：有一个左括号可以匹配，left_rem -= 1；
  • 否则：这个右括号多余，right_rem += 1。

扫描结束后，left_rem 和 right_rem 就是「最少需要删除的左括号数」和「最少需要删除的右括号数」。

2. DFS 中 balance 的作用

balance 表示当前路径中未匹配的 ( 数量。

• 遇到 (：balance += 1；
• 遇到 )：必须 balance > 0 才能保留，balance -= 1。

这样可以保证任意前缀中 ) 的数量不超过 ( 的数量，字符串合法。

3. 用 set 去重

删除不同位置的相同括号可能得到相同的字符串，用 set 自动去重，最后转成列表返回。

4. BFS 中的「连续相同括号」跳过

if i > 0 and string[i] == string[i - 1]:
    continue

避免同一层产生大量重复字符串，提高效率。

5. 特殊情况 s = ")("

• left_rem = 1，right_rem = 1；
• DFS 删掉 ) 和 (，得到 ""，合法。

答案 [""]。

---

总结

• 预处理：先扫一遍得到 left_rem / right_rem，明确最少删除数量；
• DFS + 剪枝（推荐）：
  • 对每个字符决定删除或保留；
  • 用 l_rem / r_rem 控制删除数量；
  • 用 balance 保证合法性；
  • 到达末尾且 l_rem == r_rem == balance == 0 时收集答案；
  • 用 set 去重；
• BFS：
  • 每层删一个括号，用 set 去重；
  • 首次出现合法字符串的层即为答案；
• 时间：两种方法都是指数级，但括号数量最多 20，实际很快；
• 通用套路：「最少删除 + 求所有方案」→ DFS 按字符选择 + 剪枝，或 BFS 逐层删除。

相关题目

• LC 20. 有效的括号（栈判断合法性）
• LC 22. 括号生成（回溯生成）
• LC 32. 最长有效括号（DP / 栈）
• LC 678. 有效的括号字符串（允许 * 通配）
• LC 1249. 移除无效的括号（只求一个解，栈 + 标记）