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

1. 题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 字符串中可能包含小写字母或其它字符。
• 你需要删除最少数量的括号，并返回所有可能的结果。

2. 题目理解与初步分析

什么是“有效的括号字符串”？

• 左括号 '(' 和右括号 ')' 数量匹配；
• 且从左到右遍历时，任意位置左括号数量不少于右括号数量（即不会出现未匹配的右括号）。

问题核心：

• 字符串 s 中有些括号是多余的，需要删除；
• 要求删除数量最少，并找出所有删除后的有效字符串。

难点：

• 删除哪些括号？可能有多个位置可以删除，但删除后要保证有效且删除数最少；
• 直接枚举所有删除组合会超时（因为字符串长度最多 25，但暴力枚举所有子集是 O(2^n) 可能较大）；
• 需要剪枝。

3. 思路推导：如何知道最少删除几个括号？

我们可以先遍历一次字符串，找出最少需要删除的左括号数和右括号数。

方法：

• 用 lRemove 记录需要删除的多余左括号数；
• 用 rRemove 记录需要删除的多余右括号数。

遍历时：

• 遇到 '('，左括号计数 leftCount++；
• 遇到 ')'，如果 leftCount > 0，说明有左括号匹配，则 leftCount--；否则说明这个右括号是多余的，rRemove++。

遍历结束后，leftCount 就是还剩下的未匹配的左括号数，也就是需要删除的左括号数 lRemove = leftCount。

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

• 遍历：
  • i=0: '(' → leftCount=1
  • i=1: ')' → leftCount=0
  • i=2: '(' → leftCount=1
  • i=3: ')' → leftCount=0
  • i=4: ')' → 此时 leftCount=0，所以 rRemove=1
  • i=5: '(' → leftCount=1
  • i=6: ')' → leftCount=0
• 最后 leftCount=0，所以 lRemove=0，rRemove=1。
• 最少删除：0 个左括号 + 1 个右括号。

4. 回溯搜索所有可能结果

我们知道要删除 lRemove 个左括号和 rRemove 个右括号，那么我们可以用 DFS（回溯）来尝试删除哪些括号。

DFS 设计：

• 参数：当前字符串 str，当前遍历位置 index，当前左括号计数 leftCount，当前右括号计数 rightCount，剩余待删除左括号数 lRemove，剩余待删除右括号数 rRemove。
• 每一步：
  1. 如果 lRemove == 0 且 rRemove == 0，检查当前字符串是否有效，有效则加入结果集。
  2. 从 index 开始遍历：
     • 如果遇到连续相同的括号，为了避免重复结果，只删除第一个（跳过重复）。
     • 如果当前字符是 '(' 且 lRemove > 0，尝试删除它，递归。
     • 如果当前字符是 ')' 且 rRemove > 0，尝试删除它，递归。
  3. 如果不删除，则更新 leftCount 和 rightCount，并检查有效性（如果右括号多于左括号则剪枝）。

有效性检查：

• 在 DFS 过程中，维护 leftCount 和 rightCount，如果 rightCount > leftCount，说明已经无效，剪枝。
• 最终在叶子节点时，再检查一次 leftCount == rightCount。

5. 详细步骤（以示例 s = "()())()" 为例）

1. 计算 lRemove, rRemove：lRemove=0, rRemove=1。
2. DFS 开始：
   • 初始：str="()())()", index=0, leftCount=0, rightCount=0, lRemove=0, rRemove=1。
   • 遍历到 index=0: '('，不删除（因为 lRemove=0），leftCount=1。
   • index=1: ')'，不删除，rightCount=1，leftCount=1，有效。
   • index=2: '('，不删除，leftCount=2。
   • index=3: ')'，不删除，rightCount=2，leftCount=2，有效。
   • index=4: ')'，此时 rRemove=1，尝试删除它：
     • 删除后字符串为 "()()()"，继续遍历到结束，检查有效，加入结果。
     • 回溯，不删除这个右括号，则 rightCount=3，leftCount=2，此时 rightCount>leftCount，无效，剪枝。
   • 其他分支类似。

最终得到 ["(())()","()()()"]。

6. 代码实现（Python 风格伪代码）

def removeInvalidParentheses(s):
    # 1. 计算需要删除的左右括号数
    lRemove, rRemove = 0, 0
    leftCount = 0
    for ch in s:
        if ch == '(':
            leftCount += 1
        elif ch == ')':
            if leftCount > 0:
                leftCount -= 1
            else:
                rRemove += 1
    lRemove = leftCount

    res = set()

    def dfs(idx, leftCur, rightCur, lRem, rRem, path):
        if idx == len(s):
            if lRem == 0 and rRem == 0 and leftCur == rightCur:
                res.add(path)
            return
        # 如果剩余字符数不够删，剪枝
        if len(s) - idx < lRem + rRem:
            return
        ch = s[idx]
        # 尝试删除当前字符（如果是括号）
        if ch == '(' and lRem > 0:
            dfs(idx + 1, leftCur, rightCur, lRem - 1, rRem, path)
        elif ch == ')' and rRem > 0:
            dfs(idx + 1, leftCur, rightCur, lRem, rRem - 1, path)
        # 不删除
        if ch == '(':
            dfs(idx + 1, leftCur + 1, rightCur, lRem, rRem, path + ch)
        elif ch == ')':
            if leftCur > rightCur:
                dfs(idx + 1, leftCur, rightCur + 1, lRem, rRem, path + ch)
        else:  # 字母
            dfs(idx + 1, leftCur, rightCur, lRem, rRem, path + ch)

    dfs(0, 0, 0, lRemove, rRemove, "")
    return list(res)

7. 复杂度分析

• 最坏情况：字符串全是括号，需要尝试删除某些括号，但通过剪枝（连续相同括号只删第一个、提前判断剩余字符数不够删）可以大大减少搜索空间。
• 时间复杂度：O(2^n) 理论上界，但剪枝后实际运行可接受（n ≤ 25）。
• 空间复杂度：O(n²) 因为递归栈深度和字符串拼接。

8. 总结

本题的关键点：

1. 先计算最少删除的左右括号数，缩小搜索范围。
2. 使用 DFS 回溯尝试删除，注意去重（连续相同括号只删第一个）。
3. 在 DFS 过程中维护当前左右括号计数，及时剪枝无效路径。

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