LeetCode无效括号删除：DFS回溯算法详解

1. 问题背景与核心挑战

这道LeetCode题目要求我们删除最少数量的无效括号，使得输入字符串变得有效。所谓有效括号字符串，需要满足以下条件：

1. 左括号和右括号数量相等
2. 每个右括号都能找到对应的左括号

我最初看到这个题目时，觉得它比常规的括号匹配问题复杂得多。常规问题只需要用栈就能解决，但这里需要考虑所有可能的删除组合，还要保证删除数量最少。这让我意识到需要更系统的解法设计。

2. 解法思路分析与选择

2.1 暴力解法与优化空间

最直观的想法是生成所有可能的子字符串，然后检查它们的有效性。对于一个长度为n的字符串，这样的时间复杂度是O(2^n)，显然不适用于较长的输入。

经过思考，我发现可以优化：

1. 先计算出需要删除的最少左括号和右括号数量
2. 在回溯过程中利用这个信息进行剪枝
3. 避免生成重复的有效字符串

2.2 BFS与DFS的选择

这个问题既可以用BFS也可以用DFS解决。我最终选择了DFS+回溯的方式，因为：

• BFS需要存储大量中间状态，空间复杂度较高
• DFS可以更好地利用剪枝条件
• 对于某些测试用例，DFS可能更快找到解

3. 详细解法实现

3.1 预处理计算最小删除数量

python复制def calculate_min_removal(s):
    left_rem = 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
    return left_rem, right_rem

这个预处理步骤非常关键，它告诉我们最少需要删除多少个左括号和右括号才能使字符串有效。

3.2 回溯算法实现

python复制def removeInvalidParentheses(s):
    left_rem, right_rem = calculate_min_removal(s