1. 问题背景与核心挑战
遇到需要从字符串中删除无效括号的算法题时,很多开发者会陷入暴力枚举的误区。这道LeetCode难题(编号301)的特别之处在于,它要求我们找出所有可能的有效括号组合,而不仅仅是判断有效性。想象一下你面前有一串被胡乱嵌套的括号,就像纠缠在一起的耳机线,我们需要找到所有能把它理顺的方法。
括号匹配问题在编译器设计、表达式求值等领域有广泛应用。比如在IDE中检测代码语法错误时,就需要快速定位不匹配的括号。这道题的难点在于:
- 需要处理两种括号类型(虽然原题只有小括号,但思路可扩展)
- 要求返回所有可能解而非单一解
- 字符串长度可能达到25个字符,暴力解法时间复杂度难以承受
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 解法思路与算法选择
2.1 暴力DFS的局限性
最直观的想法是用DFS遍历所有可能的子序列,然后检查每个子序列是否有效。对于长度为n的字符串,这种解法时间复杂度是O(2^n),当n=25时会有超过3000万种可能,显然不可行。
关键观察:我们可以通过预处理计算出需要删除的最少左括号和右括号数量,大幅减少搜索空间
2.2 优化后的回溯算法
更聪明的做法是先扫描字符串,统计需要删除的左右括号数量。具体步骤:
-
第一次遍历:
- 遇到'('时,left_need加1
- 遇到')'时,若left_need>0则减1,否则right_need加1
-
回溯过程中维护:
- 当前构建的字符串
- 剩余可删除的左右括号数量
- 当前开闭括号的平衡状态
python复制def removeInvalidParentheses(s):
left_remove, right_remove = 0, 0
for ch in s:
if ch == '(':
left_remove += 1
elif ch == ')':
if left_remove > 0:
left_remove -= 1
else:
right_remove += 1
result = set()
def
