1. 问题背景与核心挑战
LeetCode第301题"删除无效的括号"是一个经典的字符串处理问题,要求从给定的字符串中删除最少数量的无效括号,使剩下的字符串有效。这个问题看似简单,实则暗藏多个技术难点:
- 括号匹配的复杂性:需要处理多种无效情况(多余左括号、多余右括号、交错不匹配)
- 最小删除原则:必须确保删除的括号数量绝对最少
- 结果去重:不同删除路径可能产生相同有效字符串
我在实际解题过程中发现,许多初学者容易陷入暴力枚举的陷阱。比如直接尝试所有可能的删除组合,这种方法时间复杂度高达O(2^n),当输入字符串较长时(超过20个字符),计算时间会呈指数级增长。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 算法思路解析
2.1 回溯算法优化方案
经过多次实践验证,我发现采用带剪枝的回溯算法是最优解。核心思路分为两个阶段:
- 计算最小删除数量:
python复制def get_min_removal(s):
left = right = 0
for ch in s:
if ch == '(':
left += 1
elif ch == ')':
if left > 0: left -= 1
else: right += 1
return left + right
- 回溯生成有效字符串:
python复制def backtrack(s, index, left_count, right_count, left_rem, right_rem, path, result):
if index == len(s):
if left_rem == 0 and right_rem == 0:
result.add(''.join(path))
return
ch = s[index]
# 两种情况:删除当前字符或保留
# 删除分支(仅当当前字符是括号且还有删除额度时)
if (ch == '(' and left_rem > 0) or (ch == ')' and right_rem > 0):
