1. 问题背景与核心思路
遇到LeetCode上"删除无效的括号"这道题时,很多Python选手会被它的多重判断条件绕晕。这道题在字节跳动、亚马逊等大厂面试中高频出现,考察的是对DFS/BFS算法的灵活运用和边界条件处理能力。
题目要求我们删除最少数量的无效括号,使输入字符串变得有效。这里的"有效"需要满足两个条件:一是左右括号数量相等,二是括号嵌套关系正确。比如"()())()"的合法解可以是["(())()","()()()"],而"(a)())()"的解则包含["(a())()","(a)()()"]。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 暴力DFS解法与优化
2.1 基础DFS实现
最直观的解法是用DFS生成所有可能的子串,然后检查有效性。这种方法虽然直接,但时间复杂度高达O(2^n),在n=25时就会超时:
python复制def removeInvalidParentheses(s):
def is_valid(t):
cnt = 0
for c in t:
if c == '(': cnt += 1
elif c == ')': cnt -= 1
if cnt < 0: return False
return cnt == 0
level = {s}
while True:
valid = list(filter(is_valid, level))
if valid: return valid
level = {s[:i]+s[i+1:] for s in level for i in range(len(s))}
2.2 剪枝优化策略
我们可以通过预计算需要删除的左右括号数量来优化。先遍历字符串,统计需要删除的左右括号数:
python复制left_remove = right_remove = 0
for ch in s:
if ch == '(':
left_remove += 1
elif ch == ')':
if left_remove > 0:
