1. 问题背景与核心挑战
今天想和大家分享一道LeetCode上的经典难题——"删除无效的括号"（题目编号301）。这道题在各大科技公司的面试中出现频率很高，特别是考察候选人对DFS/BFS算法的掌握程度以及对边界条件的处理能力。我第一次遇到这个问题时，花了整整一个下午才理清思路，现在把完整的解题思路和优化过程整理出来。
这个问题的核心是：给定一个由括号和小写字母组成的字符串，我们需要删除最少数量的无效括号，使剩下的字符串有效。所谓有效括号字符串，需要满足两个条件：1) 所有左括号和右括号正确匹配；2) 每个右括号都有对应的左括号。
2. 解题思路分析
2.1 暴力解法与复杂度分析
最直观的想法是生成所有可能的子字符串，然后检查它们是否是有效的。对于一个长度为n的字符串，每个字符都有"保留"或"删除"两种选择，所以总共有2^n种可能的子字符串。对于每个子字符串，我们需要O(n)的时间来验证其有效性，因此总时间复杂度是O(n*2^n)。
这种方法在小规模输入时勉强可用，但当n>20时就完全不可行了。以n=20为例，2^20≈100万，再乘以20就是2000万次操作，这在LeetCode上肯定会超时。
2.2 优化思路：剪枝与提前终止
我们可以通过以下几个观察来优化算法：
-
我们可以预先计算出需要删除的最少左括号和右括号数量。遍历字符串时：
- 遇到'('时，left_need加1
- 遇到')'时，如果left_need>0则减1，否则right_need加1
-
在递归过程中，我们可以跟踪当前的括号平衡状态。如果出现balance<0的情况（即右括号多于左括号），就可以立即终止当前分支的探索。
-
对于连续的相同括号，我们只需要考虑删除其中一个，避免生成重复的结果。
3. Python实现详解
3.1 预处理与初始化
python复制def removeInvalidParentheses(s):
# 计算需要删除的最少左右括号数
left_remove = right_remove = 0
for char in s:
if char == '(':
left_remove += 1
elif char == ')':
if left_remove > 0:
left_remove -= 1
else:
right_remove += 1
result = set()
dfs(s, 0, 0, 0, left_remove, right_remove, [], result)
return list(result)
3.2 DFS核心实现
python复制def dfs(s, index, left_count, right_count, left_remove, right_remove, path, result):
if index == len(s):
if left_remove == 0 and right_remove == 0:
result.add(''.join(path))
return
char = s[index]
# 情况1：删除当前字符（如果是括号）
if char == '(' and left_remove > 0:
dfs(s, index+1, left_count, right_count, left_remove-1, right_remove, path, result)
if char == ')' and right_remove > 0:
dfs(s, index+1, left_count, right_count, left_remove, right_remove-1, path, result)
# 情况2：保留当前字符
path.append(char)
if char not in '()':
dfs(s, index+1, left_count, right_count, left_remove, right_remove, path, result)
elif char == '(':
dfs(s, index+1, left_count+1, right_count, left_remove, right_remove, path, result)
elif char == ')' and left_count > right_count:
dfs(s, index+1, left_count, right_count+1, left_remove, right_remove, path, result)
path.pop()
3.3 关键点解析
-
使用集合存储结果：因为不同的删除方式可能产生相同的有效字符串，使用set可以自动去重。
-
路径管理：使用path列表来记录当前选择的字符，通过append和pop操作实现回溯。
-
平衡条件检查：只有在左括号数量大于右括号数量时，才会考虑保留右括号。
4. 复杂度优化与BFS解法
4.1 DFS的局限性
虽然DFS加剪枝已经比暴力解法高效很多，但在最坏情况下（比如全是括号的字符串），时间复杂度仍然是指数级的。这时可以考虑使用BFS解法。
4.2 BFS实现思路
BFS的思路是逐层删除括号，在每一层中删除一个括号，然后检查是否得到有效字符串。因为我们要找的是删除最少括号的解，所以BFS找到的第一个有效解就是最优解。
python复制from collections import deque
def removeInvalidParenthesesBFS(s):
def is_valid(t):
balance = 0
for char in t:
if char == '(':
balance += 1
elif char == ')':
balance -= 1
if balance < 0:
return False
return balance == 0
queue = deque([s])
visited = set([s])
result = []
found = False
while queue:
level_size = len(queue)
for _ in range(level_size):
current = queue.popleft()
if is_valid(current):
result.append(current)
found = True
if found:
continue
for i in range(len(current)):
if current[i] not in '()':
continue
next_str = current[:i] + current[i+1:]
if next_str not in visited:
visited.add(next_str)
queue.append(next_str)
if found:
break
return result if result else [""]
4.3 BFS与DFS的选择
- BFS优势：在存在多个解时，BFS能更快找到删除最少括号的解，适合大多数情况。
- DFS优势：当字符串很长但无效括号很少时，DFS可能更高效，因为它可以更精确地控制删除的括号数量。
5. 常见错误与调试技巧
5.1 典型错误案例
-
忘记处理连续相同括号：比如"())())"，如果不处理连续括号，会产生很多重复解。
-
平衡条件判断错误：在DFS中，保留右括号的条件是left_count > right_count，而不是left_remove > 0。
-
过早终止：在BFS中，找到第一个有效解后应该完成当前层的处理，而不是立即返回。
5.2 调试建议
-
打印中间状态：在递归函数中加入打印语句，输出当前的index、path和balance状态。
-
小规模测试：先用简单案例测试，如"()())()"，确保基础逻辑正确。
-
边界测试：测试全括号字符串"(((((", 无括号字符串"abc"，以及空字符串""。
6. 性能优化进阶
6.1 预处理优化
在DFS解法中，我们可以先进行一次遍历，找出必须保留的括号。例如，字符串开头的一系列")"肯定是要删除的，结尾的"("也是要删除的。
6.2 双向搜索
对于特别长的字符串，可以考虑从两端同时进行搜索，减少搜索空间。这种方法实现较复杂，但在极端情况下能显著提升性能。
6.3 动态规划尝试
虽然这个问题不太适合标准的动态规划解法，但可以尝试用memoization来缓存中间结果，避免重复计算。不过在实践中，由于有效解通常不多，这种优化的效果有限。
7. 实际面试中的应对策略
当面试中被问到这个问题时，建议采取以下步骤：
- 先明确问题要求，给出几个例子说明输入输出
- 提出暴力解法并分析复杂度
- 逐步引入优化思路（计算最少删除数、剪枝等）
- 先实现DFS版本，再讨论BFS版本
- 分析时间空间复杂度
- 提出可能的进一步优化方向
记住要边写代码边解释，特别是边界条件的处理。面试官通常更关注你的思考过程，而不是一次写出完美代码。