LeetCode 301. 删除无效的括号

1. 题目描述

给你一个由括号 '('、')' 和字母组成的字符串 s，要求你删除最少数量的无效括号，使得字符串变得有效（即每个左括号 '(' 都有对应的右括号 ')' 匹配，且括号顺序正确）。
你需要返回所有可能的结果（任意顺序），且结果中不能包含重复的字符串。

示例 1
输入：s = "()())()"
输出：["(())()","()()()"]
说明：删除一个括号可以得到两个有效字符串。

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

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

提示

• 字符串可能包含字母，括号只包含 '(' 和 ')'
• 需要删除最少的括号数量
• 返回所有可能的结果（可能多个）

2. 问题分析

有效括号的定义

1. 左括号数量等于右括号数量
2. 从左到右遍历时，右括号的数量不能超过左括号数量（否则出现无法匹配的右括号）

关键难点

1. 不知道要删除哪些括号 → 需要搜索
2. 要删除最少括号 → 可以按删除数量递增进行搜索（BFS 思路）
3. 可能存在多个结果且不能重复 → 需要去重
4. 包含字母，字母不影响括号匹配，不能删除

核心思路

• 先计算出最少需要删除的左括号数和右括号数
• 然后通过 DFS 回溯，在搜索过程中保证不产生无效的中间状态，并最终得到有效字符串

3. 计算最少需要删除的括号数量

遍历一次字符串：

• 遇到 '('：左括号计数 +1
• 遇到 ')'：
  • 如果当前左括号计数 > 0，说明有左括号可以匹配，则左括号计数 -1
  • 否则这个右括号是多余的，右括号删除计数 +1
• 遍历结束后，左括号计数中剩余的也是多余的，需要删除。

示例：s = "()())()"
过程：

• 初始 leftCount = 0, removeLeft = 0, removeRight = 0
• 遍历：
  '(' → leftCount=1
  ')' → leftCount=0
  '(' → leftCount=1
  ')' → leftCount=0
  ')' → 此时 leftCount=0，removeRight=1
  '(' → leftCount=1
  ')' → leftCount=0
  结束：leftCount=0，removeLeft=0，removeRight=1
  所以最少删除 1 个右括号。

4. DFS 回溯法设计

我们已知：

• 需要删除的多余左括号数 removeLeft
• 需要删除的多余右括号数 removeRight
• 最终有效的字符串中，左括号数等于右括号数

DFS 参数：

• index：当前处理到原字符串的位置
• leftCount：当前已生成的字符串中左括号比右括号多出的数量（必须 >=0）
• removeL：还需要删除的左括号数量
• removeR：还需要删除的右括号数量
• current：当前已生成的字符串

搜索策略：

1. 如果 index == s.length()，检查是否 removeL == 0、removeR == 0 且 leftCount == 0，满足则保存结果
2. 当前字符是 '('：
   • 如果 removeL > 0，可以选择删除这个左括号（removeL-1，不加入 current）
   • 可以选择保留这个左括号（leftCount+1，加入 current）
3. 当前字符是 ')'：
   • 如果 removeR > 0，可以选择删除这个右括号
   • 如果 leftCount > 0，可以选择保留这个右括号（leftCount-1，加入 current）
     注意：必须先检查 leftCount > 0 才能保留，否则会形成无效字符串
4. 当前字符是字母：必须保留，直接加入 current，继续搜索

去重：

• 在同一个位置，如果连续相同的字符出现，选择删除或保留时可能会产生重复
• 我们可以用集合记录最终结果来去重，但更高效的是在搜索时避免重复
• 对于连续的相同括号，我们优先保留第一个，后面的相同括号如果选择保留，必须保证前面的相同括号没有被删除（否则会出现重复状态）。
  一个简单的方法：当决定保留某个括号时，如果前面有相同的括号被跳过（删除），那么当前括号也应该跳过（删除），避免重复搜索。
  实际常用技巧：遇到连续相同括号时，只考虑第一个括号的删除/保留，后面的相同括号如果要保留，则必须前面的相同括号也保留，否则跳过。

5. 详细步骤举例

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

计算最少删除：removeLeft=0, removeRight=1

DFS 过程（简化描述）：

1. 从 index=0 开始，'(' 保留（leftCount=1）
2. index=1，')'，leftCount>0，可以保留（leftCount=0）
3. index=2，'('，保留（leftCount=1）
4. index=3，')'，保留（leftCount=0）
5. index=4，')'，此时：
   • removeR=1，可以删除它（removeR=0）
   • 也可以保留？但 leftCount=0，不能保留（否则无效）
     所以只能删除。
6. index=5，'('，保留（leftCount=1）
7. index=6，')'，保留（leftCount=0）
8. 结束：得到 "(())()"

另一种删除选择：
在 index=1 之后，如果删除 index=2 的 '('，则 removeL=0，但后面会遇到更多问题，可能无法得到有效结果，搜索会剪枝。

实际上，BFS 思路更直观：

• 第一层：原始字符串
• 第二层：删除 1 个括号的所有可能字符串
• 第三层：删除 2 个括号的所有可能字符串
  … 直到找到有效字符串为止。
  但 BFS 可能产生大量重复，所以常用 DFS 回溯 + 剪枝。

6. 算法实现（DFS 回溯剪枝）

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 1. 计算最少需要删除的左括号和右括号数量
        removeL, removeR = 0, 0
        leftCount = 0
        for ch in s:
            if ch == '(':
                leftCount += 1
            elif ch == ')':
                if leftCount > 0:
                    leftCount -= 1
                else:
                    removeR += 1
        removeL = leftCount  # 剩余未匹配的左括号也要删除
        
        # 2. DFS 回溯
        res = set()
        
        def dfs(index, leftCount, removeL, removeR, current):
            if index == len(s):
                if removeL == 0 and removeR == 0 and leftCount == 0:
                    res.add(current)
                return
            
            ch = s[index]
            if ch == '(':
                # 删除这个左括号
                if removeL > 0:
                    dfs(index+1, leftCount, removeL-1, removeR, current)
                # 保留这个左括号
                dfs(index+1, leftCount+1, removeL, removeR, current+ch)
            elif ch == ')':
                # 删除这个右括号
                if removeR > 0:
                    dfs(index+1, leftCount, removeL, removeR-1, current)
                # 保留这个右括号（必须左括号多于右括号）
                if leftCount > 0:
                    dfs(index+1, leftCount-1, removeL, removeR, current+ch)
            else:  # 字母
                dfs(index+1, leftCount, removeL, removeR, current+ch)
        
        dfs(0, 0, removeL, removeR, "")
        return list(res)

7. 优化去重

上面的 DFS 在遇到连续相同括号时，会产生重复结果，所以用 set 去重。
更高效的剪枝：

• 当有连续相同括号时，如果要删除，则删除第一个即可，后面的相同括号如果也删除，会产生重复
• 改进：在删除时，如果当前字符和上一个字符相同，且上一个字符没有被保留，则跳过本次删除（因为之前已经处理过）

优化版本（部分逻辑）：
实际更常见的写法是在递归循环中，如果当前字符和上一个字符相同，则跳过删除选择（只保留一种删除情况）。
这里为了清晰，给出另一种常见写法（BFS 也可行，但 DFS 更节省空间）。

8. 总结

核心要点：

1. 先计算最少需要删除的左右括号数量
2. 使用 DFS 回溯，尝试删除或保留每个括号
3. 剪枝条件：
   • 保留右括号时，必须保证已生成的字符串中左括号多于右括号
   • 最终字符串必须左括号数等于右括号数
4. 去重：用集合或在搜索中跳过相同字符的重复删除

时间复杂度：最坏情况是每个括号都尝试删除/保留，O(2^n)，但剪枝后实际运行较快
空间复杂度：O(n) 递归深度，加上结果存储

这样就能找出所有删除最少括号后得到的有效括号字符串。