DFS与剪枝优化解决括号匹配问题

1. 问题背景与核心挑战

遇到字符串处理问题时，括号匹配是个经典难题。LeetCode上"删除无效的括号"这道hard题目，要求我们删除最少数量的无效括号，使输入字符串变得有效。初次看到这个题目时，我花了整整一个下午才理清思路——这不仅仅是简单的栈应用，还需要考虑多种可能的分支情况。

无效括号的判断标准很明确：每个左括号必须对应一个右括号，且括号必须正确嵌套。但难点在于，当存在多个无效位置时，我们需要找出所有可能的合法组合。例如字符串"()())()"就有两种有效解：["()()()", "(())()"]。这种需要穷举可能性又要求最优解的问题，通常需要DFS/BFS与剪枝策略的结合。

2. 解法思路分析与选择

2.1 暴力DFS的局限性

最直观的想法是用深度优先搜索尝试所有可能的删除组合。对于每个字符，我们有两种选择：保留或删除。对于长度为n的字符串，这种暴力方法的时间复杂度是O(2^n)。当n=25时，这相当于约3300万次操作——在LeetCode上必然超时。

我在本地测试时发现，即使加入简单的提前终止条件（如剩余字符已少于当前最优解长度），对于案例"((((((((((((((((((((((((("仍然需要近10秒才能返回。这说明纯暴力方法不可行。

2.2 关键优化思路

有效的优化需要从问题特性入手：

1. 可以预先计算出需要删除的左括号和右括号的最小数量
2. 在DFS过程中实时跟踪括号的平衡状态
3. 遇到连续重复字符时可以跳过重复计算

具体实现时，我采用了两轮预处理：

• 第一轮遍历确定最少需要删除的左右括号数
• 第二轮DFS带着这些约束条件进行搜索

这种方法将时间复杂度降到了O(2^l)，其中l是最少需要删除的括号数。对于大多数测试用例，l通常不超过5，这使得算法实际运行时间在毫秒级。

3. Python实现详解

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 lef