题目描述
思路解析动画文字版
硬枚举所有删除组合？会爆炸，而且分不清谁删得最少。
关键一句话：BFS 的层数就是删除次数，第一层出现合法串，就是删得最少。
第 0 层：只有原串一个状态：起点：第 0 层只有原串本身，代表「一个都没删」。先看它合不合法。
灵魂帧 · 怎么判合法：扫一遍记 balance：判合法只要一个计数器。左括号加一、右括号减一。扫到下标 4 这个右括号，balance 掉到负一，右括号提前多出来，非法。
灵魂帧 · 展开第 1 层：逐位删一个括号：第 1 层怎么来？把原串每一位括号轮流删掉一次，得到七个新串。删第 3 位和第 4 位都得到同一个，所以要去重。
第 1 层候选：每格都删了 1 个括号：去重后第 1 层剩六个候选，每个都只删了一个括号。现在逐个检查它们合不合法。
命中候选 1："(())()" 合法，进 ans：检查候选 1。它的 balance 一路非负、最后回到零，合法。第一次命中，收进答案。
命中候选 3："()()()" 同层也合法：再看候选 3，也合法。题目要所有最少删除的结果，所以同一层合法的都收，现在答案有两个。
同层非法候选：过滤掉，不再往下展开：剩下四个候选 balance 会变负，非法。本层已有答案，它们不必再删一个往第 2 层走了。
本层有答案，立刻返回：第 1 层已经凑出合法串，直接返回这两个。继续到第 2 层只会删得更多，没必要。
灵魂帧慢放 · 把 "()())()" 整条链重放一遍：慢放整条链：原串非法，删一个生成六个候选，候选 1 和 3 合法就停。删除次数正好是层数，等于一。
边界样例 ")("：要删到第 2 层才合法：看个极端例子。右括号在前的 )( 怎么删都得删两个：第 1 层只剩单个括号还是非法，第 2 层删成空串才合法。空串是合法括号串。
记住这句：最少操作还要所有最短解，BFS 分层是最自然的建模。
边界三连：三个极端：本来合法零删除、纯字母直接过、最坑的 )( 要删空。
面试追问：面试别只背 BFS，能补一句「DFS 配额删 + 剪枝」的优化方向是加分项。
迁移阶梯：把它练到能复述后，去 ds 图论专题里迁移：换个「一步改动」的定义，同一套 BFS 分层就能套到单词接龙这类题。
进阶提示：BFS 是入门款。真正面试想拿满分，去研究「配额 DFS + 剪枝」这套快解。
参考代码
class Solution: def removeInvalidParentheses(self, s): def valid(t): bal = 0 for ch in t: if ch == '(': bal += 1 elif ch == ')': bal -= 1 if bal < 0: return False return bal == 0 level = {s} while True: ans = [t for t in level if valid(t)] if ans: return ans nxt = set() for t in level: for i, ch in enumerate(t): if ch in '()': nxt.add(t[:i] + t[i + 1:]) level = nxt复杂度
- 时间复杂度：O(2^n · n)，n 为串长。最坏要枚举大量删除子集（每位删/不删 → 2^n），每个候选 valid 线性扫一遍。题目限制 n ≤ 25 才能跑。
- 空间复杂度：O(2^n · n)，去重的 set 和当前层最多存指数级个候选串，每串长 O(n)。
可套用的代码模板
把本题抽成骨架：只要填 isGoal（本题 = valid）和 neighbors（本题 = 删一个括号），这套分层 BFS 就能套到一类「最少操作」题。右上角可切 C++ / Java。
# 通用：最少操作 + 返回所有最短解from collections import dequedef min_ops_all(start): level = { start } # 第 0 层 while level: ans = [s for s in level if is_goal(s)] # ← 填：本层达标的状态 if ans: return ans # 第一层命中即最少 nxt = set() # set 去重是命门 for s in level: for ns in neighbors(s): # ← 填：一步改动能到的状态 nxt.add(ns) level = nxt # 进入下一层 = 多操作一次 return []易错点
面试追问把动画讲成自己的话
追问为什么 BFS 能保证删除次数最少？
追问能不能不用 BFS，改成 DFS/回溯？
追问valid 怎么判合法？
追问时间复杂度怎么估？为什么能过？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题