LeetCode 301题解析：删除无效括号的DFS/BFS优化策略

1. 问题背景与核心挑战

LeetCode第301题"删除无效的括号"是算法面试中的经典难题，要求从包含括号和其他字符的字符串中，删除最少数量的无效括号，使剩余的字符串有效。这道题在亚马逊、Facebook等大厂面试中出现频率较高，考察的是对DFS/BFS算法的灵活运用和边界条件处理能力。

字符串有效性的判定标准很简单：左括号和右括号数量相等，且在任何前缀中左括号数量不少于右括号。但难点在于如何高效找出所有可能的有效组合。例如输入"()())()"，正确输出应该包含["(())()","()()()"]两种解。

2. 算法选择与复杂度分析

2.1 暴力DFS解法

最直观的方法是尝试删除每一个括号，通过DFS递归验证有效性。这种方法时间复杂度为O(2^N)，对于长度超过20的字符串就会非常慢。实际面试中这种解法只能作为思路起点。

python复制def removeInvalidParentheses(s):
    def is_valid(s):
        count = 0
        for char in s:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0
    
    level = {s}
    while True:
        valid = list(filter(is_valid, level))
        if valid:
            return valid
        level = {s[:i] + s[i+1:] for s in level for i in range(len(s)) if s[i] in '()'}

2.2 优化后的BFS解法

更高效的方案是使用BFS逐层删除括号。每一层删除一个括号，直到找到有效解。这种方法可以保证找到的是删除最少括号的解，时间复杂度优化到O(N×2^N)。

python复制from collections import deque

def removeInvalidParentheses(s):
    def is_valid(s):
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
            elif c == ')':
                cnt -= 1
                if cnt < 0:
                    return False
        return cnt == 0
    
    queue = deque([s])
    visited = set([s])
    found = False
    res = []
    
    while queue:
        curr = queue.popleft()
        if is_valid(curr):
            res.append(curr)
            found = True
        
        if found:
            continue
            
        for i in range(len(curr)):
            if curr[i] not in '()':
                continue
            next_str = curr[:i] + curr[i+1:]
            if next_str not in visited:
                visited.add(next_str)
                queue.append(next_str)
    
    return res if res else ['']

3. 关键优化技巧

3.1 提前计算需要删除的括号数

通过预处理可以确定需要删除的左括号和右括号的最小数量，从而减少不必要的计算：

python复制def calculate_removal(s):
    left_rem = right_rem = 0
    for char in s:
        if char == '(':
            left_rem += 1
        elif char == ')':
            if left_rem > 0:
                left_rem -= 1
            else:
                right_rem += 1
    return left_rem, right_rem

3.2 剪枝策略

在DFS过程中，可以根据当前括号的平衡状态进行剪枝：

1. 如果剩余字符数不足以删除所需数量的括号，直接返回
2. 如果当前前缀的右括号已经多于左括号，后续不可能有效
3. 连续重复括号只需处理第一个，避免重复计算

4. 完整优化解法

结合上述优化，最终的DFS解法如下：

python复制def removeInvalidParentheses(s):
    res = []
    left_rem, right_rem = calculate_removal(s)
    
    def backtrack(s, index, left_count, right_count, left_rem, right_rem, path):
        if index == len(s):
            if left_rem == 0 and right_rem == 0:
                res.append(''.join(path))
            return
        
        char = s[index]
        # 情况1：删除当前字符（如果是括号）
        if char == '(' and left_rem > 0:
            backtrack(s, index+1, left_count, right_count, left_rem-1, right_rem, path)
        elif char == ')' and right_rem > 0:
            backtrack(s, index+1, left_count, right_count, left_rem, right_rem-1, path)
        
        # 情况2：保留当前字符
        path.append(char)
        if char not in '()':
            backtrack(s, index+1, left_count, right_count, left_rem, right_rem, path)
        elif char == '(':
            backtrack(s, index+1, left_count+1, right_count, left_rem, right_rem, path)
        elif char == ')' and left_count > right_count:
            backtrack(s, index+1, left_count, right_count+1, left_rem, right_rem, path)
        path.pop()
    
    backtrack(s, 0, 0, 0, left_rem, right_rem, [])
    return list(set(res)) if res else ['']

5. 测试用例与边界处理

完整的解决方案需要考虑以下边界情况：

1. 空字符串输入
2. 没有无效括号的情况
3. 全是左括号或右括号
4. 包含其他字符的情况
5. 多个连续相同括号的情况

python复制test_cases = [
    ("()())()", ["(())()","()()()"]),
    ("(a)())()", ["(a())()","(a)()()"]),
    (")(", [""]),
    ("n", ["n"]),
    ("(((", [""]),
    (")))", [""])
]

6. 性能对比与选择建议

实际面试中建议：

1. 先说明暴力解法思路
2. 提出BFS优化方案
3. 最后给出带剪枝的DFS解法
4. 讨论各种方法的trade-off

7. 常见错误与调试技巧

1. 重复结果问题：使用集合存储结果去重
2. 超时问题：确保实现了有效的剪枝策略
3. 漏解问题：检查递归终止条件和结果收集逻辑
4. 错误识别有效字符串：单独测试is_valid函数

调试时可以：

• 打印递归树和当前路径
• 跟踪剩余需要删除的括号数
• 验证中间结果的正确性

关键提示：在实现DFS时，path数组的pop()操作必须与append()严格对应，这是回溯算法中最容易出错的地方之一。建议在纸上画出递归树帮助理解执行流程。