1. 问题背景与核心挑战
LeetCode上"删除无效的括号"是一道经典的字符串处理题目,编号为301。这道题要求我们从一个包含括号和其他字符的字符串中,删除最少数量的无效括号,使得剩余的字符串成为有效的括号组合。乍看简单,实际处理时需要同时考虑多种边界情况。
我第一次遇到这个问题时,以为只需要简单统计左右括号数量就能解决。实际编写代码后发现,像"()())()"这样的输入,存在多个可能的有效结果(["()()()", "(())()"]),简单的计数法无法处理这种歧义情况。这促使我深入研究更可靠的解法。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 解法思路分析与选择
2.1 暴力回溯法的可行性
最直观的解法是生成所有可能的子字符串,然后检查每个子串是否有效。对于一个长度为n的字符串,每个字符有保留或删除两种选择,时间复杂度是O(2^n)。当n>20时,这种解法在LeetCode上会超时。
python复制def removeInvalidParentheses(s):
def isValid(sub):
balance = 0
for ch in sub:
if ch == '(': balance += 1
elif ch == ')': balance -= 1
if balance < 0: return False
return balance == 0
level = {s}
while True:
valid = list(filter(isValid, level))
if valid: return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
2.2 优化思路:有限步数删除
观察到题目要求"最少删除",这提示我们可以使用BFS逐层处理。每一层尝试删除一个括号,直到找到有效结果。这种方法在最坏情况下时间复杂度仍是O(2^n),但平均情况会好很多。
关键优化点:使用队列实现BFS时,需要记录已经处理过的字符串避免重复计算。这在测试用例包
