1. 问题背景与核心挑战
LeetCode上"删除无效的括号"这道题编号为301,属于字符串处理类难题的典型代表。题目要求我们从一个包含括号和其他字符的字符串中,删除最少数量的无效括号,使得剩余的字符串成为有效的括号组合。有效括号串的定义是每个左括号都能找到对应的右括号,并且整体嵌套关系正确。
这道题的难点主要体现在三个方面:首先,字符串中可能包含非括号字符,这些字符需要保留但增加了判断复杂度;其次,删除的位置组合存在多种可能性,常规的暴力枚举在长字符串情况下会面临指数级时间复杂度;最后,需要确保最终结果是所有可能解中删除次数最少的方案。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 算法思路解析
2.1 回溯算法基础实现
最直观的解法是采用回溯算法,系统地尝试所有可能的删除组合。基本思路是遍历字符串,在每个括号位置做出保留或删除的选择,并通过递归探索所有可能性。在这个过程中需要维护几个关键状态:
- 当前剩余的字符串
- 已经删除的括号数量
- 当前括号的平衡状态(左括号比右括号多出的数量)
回溯过程中,当遇到右括号多于左括号的情况时立即终止当前路径的探索,因为这种情况已经不可能形成有效括号串。当遍历完整个字符串后,检查括号是否平衡,并记录所有有效解中删除次数最少的方案。
python复制def removeInvalidParentheses(s):
res = []
min_removed = float('inf')
def backtrack(index, left_count, right_count, path, removed):
nonlocal min_removed, res
if index == len(s):
if left_count == right_count:
if removed < min_removed:
res = [path]
min_removed = removed
elif removed == min_removed and path not in res:
res.append(path)
return
char = s[index]
if char not in '()':
backtrack(index+1, left_count, right_count, path+char, removed)
retur
