白追追1. 问题背景与核心挑战
LeetCode第301题"删除无效的括号"是一个经典的字符串处理问题，要求从给定的包含括号的字符串中删除最少数量的无效括号，使剩余的字符串有效。这个问题在2024年各大科技公司的面试中频繁出现，特别是在考察候选人对DFS/BFS算法的理解和字符串处理能力时。
我第一次遇到这个问题是在一次模拟面试中，当时被要求用Python在30分钟内完成。实际花了45分钟才勉强通过所有测试用例，过程中发现了许多值得注意的边界情况。这个问题的难点在于：
- 需要同时处理多种无效情况：多余的左括号、多余的右括号、括号类型不匹配
- 可能存在多个有效解，需要全部返回
- 要求删除最少数量的括号，即找到最大可能的有效字符串
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 算法思路分析与选择
2.1 暴力解法与优化空间
最直观的暴力解法是生成所有可能的子字符串，然后检查每个子串是否有效。对于一个长度为n的字符串，时间复杂度是O(n*2^n)，当n=20时就已经超过百万级计算量，显然不可行。
通过分析可以发现两个关键优化点：
- 我们只需要考虑删除括号的情况，其他字符可以保留
- 可以通过预处理确定最少需要删除多少左括号和右括号
2.2 BFS与DFS的选择
这个问题适合用BFS和DFS两种方法解决：
BFS方法：
- 层级遍历，首先检查原始字符串
- 然后检查所有删除1个括号的可能
- 接着检查删除2个括号的可能...
- 一旦找到有效字符串就停止，保证删除数量最少
DFS方法：
- 先统计需要删除的左括号和右括号数量
- 递归尝试删除括号，优先处理必须删除的情况
- 通过剪枝避免重复计算
经过实际测试，DFS在Python中的表现通常更好，因为：
- Python的函数调用开销较大，BFS的队列操作成本较高
- DFS可以更早进行剪枝
- 问题本身具有递归特性，DFS代码更直观
3. DFS解法详细实现
3.1 预处理统计
首先我们需要编写一个函数统计最少需要删除的左右括号数量：
python复制def get_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
这个函数的时间复杂度是O(n)，空间复杂度是O(1)。它通过模拟括号匹配过程，统计无法匹配的左右括号数量。
3.2 核心DFS函数
python复制def removeInvalidParentheses(s):
left_rem, right_rem = get_min_removal(s)
result = set()
def dfs(index, left_count, right_count, left_rem, right_rem, expr):
if index == len(s):
if left_rem == 0 and right_rem == 0:
result.add("".join(expr))
return
ch = s[index]
# 情况1：删除当前字符（如果是括号）
if (ch == '(' and left_rem > 0) or (ch == ')' and right_rem > 0):
dfs(index + 1,
left_count,
right_count,
left_rem - (1 if ch == '(' else 0),
right_rem - (1 if ch == ')' else 0),
expr)
# 情况2：保留当前字符
expr.append(ch)
if ch not in '()':
dfs(index + 1, left_count, right_count, left_rem, right_rem, expr)
elif ch == '(':
dfs(index + 1, left_count + 1, right_count, left_rem, right_rem, expr)
elif ch == ')' and left_count > right_count:
dfs(index + 1, left_count, right_count + 1, left_rem, right_rem, expr)
expr.pop()
dfs(0, 0, 0, left_rem, right_rem, [])
return list(result)
3.3 关键点解析
- 使用集合去重：因为可能通过不同删除路径得到相同结果
- 回溯法的实现：通过
expr.append()和expr.pop()实现路径记录 - 剪枝条件：
- 只有左括号多于右括号时才能添加右括号
- 只在有剩余删除配额时才尝试删除括号
- 非括号字符的处理：直接保留，不影响括号计数
4. 测试用例与边界情况
4.1 常规测试用例
python复制print(removeInvalidParentheses("()())()"))
# 输出: ["()()()", "(())()"]
print(removeInvalidParentheses("(a)())()"))
# 输出: ["(a)()()", "(a())()"]
4.2 边界情况处理
-
空字符串输入：
python复制print(removeInvalidParentheses("")) # 输出: [""] -
无括号字符串：
python复制print(removeInvalidParentheses("abc")) # 输出: ["abc"] -
全无效括号：
python复制print(removeInvalidParentheses(")))(((")) # 输出: [""] -
嵌套括号：
python复制print(removeInvalidParentheses("(()))(()")) # 输出: ["()()", "(())"]
5. 性能优化与注意事项
5.1 时间复杂度分析
最坏情况下时间复杂度为O(2^n)，但实际通过剪枝会好很多：
- 预处理确定了必须删除的括号数量
- 递归过程中及时终止不符合条件的分支
- 使用集合自动去重
5.2 空间复杂度
主要消耗来自：
- 递归调用栈：O(n)
- 结果存储：最坏情况下可能有指数级结果
5.3 实际编码注意事项
-
字符串拼接优化：
- 使用列表而不是直接拼接字符串
- 在Python中，列表的append/pop操作比字符串拼接高效得多
-
避免重复计算：
- 预处理统计删除数量只需一次
- 不要在每个递归层级重新计算
-
剪枝条件的顺序：
- 先处理删除当前字符的情况
- 再处理保留当前字符的情况
- 这样的顺序可以减少不必要的递归调用
6. 常见错误与调试技巧
6.1 典型错误模式
-
忘记去重：
- 直接使用列表存储结果会导致重复
- 必须使用集合，最后再转为列表
-
剪枝条件不完整：
- 遗漏右括号的添加条件(left_count > right_count)
- 忘记检查删除配额(left_rem/right_rem)
-
索引越界：
- 递归终止条件必须是index == len(s)
- 不能是index >= len(s)或其他变体
6.2 调试技巧
-
打印递归树：
python复制def dfs(index, ...): print(f"Index: {index}, Expr: {''.join(expr)}") # 其余代码... -
使用小测试用例：
- 先从简单案例开始，如"())"
- 逐步增加复杂度
-
可视化括号匹配：
python复制def is_valid(s): balance = 0 for ch in s: # 可视化逻辑 if ch == '(': balance += 1 elif ch == ')': balance -= 1 if balance < 0: return False return balance == 0
7. 扩展与变种问题
7.1 只返回一个解
如果只需要返回任意一个有效解（而不是所有可能解），可以修改DFS在找到第一个解时立即返回：
python复制def removeOneValid(s):
left_rem, right_rem = get_min_removal(s)
def dfs(index, left_count, right_count, left_rem, right_rem, expr):
if index == len(s):
if left_rem == 0 and right_rem == 0:
return "".join(expr)
return None
ch = s[index]
# 尝试删除
if (ch == '(' and left_rem > 0) or (ch == ')' and right_rem > 0):
result = dfs(index + 1,
left_count,
right_count,
left_rem - (1 if ch == '(' else 0),
right_rem - (1 if ch == ')' else 0),
expr)
if result is not None:
return result
# 尝试保留
expr.append(ch)
if ch not in '()':
result = dfs(index + 1, left_count, right_count, left_rem, right_rem, expr)
elif ch == '(':
result = dfs(index + 1, left_count + 1, right_count, left_rem, right_rem, expr)
elif ch == ')' and left_count > right_count:
result = dfs(index + 1, left_count, right_count + 1, left_rem, right_rem, expr)
else:
result = None
expr.pop()
return result
return dfs(0, 0, 0, left_rem, right_rem, [])
7.2 处理多种括号类型
如果问题扩展到包含{}和[]，验证函数需要修改：
python复制def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in mapping:
top = stack.pop() if stack else '#'
if mapping[ch] != top:
return False
elif ch in '({[':
stack.append(ch)
return not stack
7.3 最小编辑距离问题
这个问题可以看作是求字符串的最小编辑距离的一种特例，其中只允许删除操作。类似的思路可以应用于其他编辑距离问题。