先说结论：这道题我在不同阶段的解法完全不一样。第一次做的时候，我傻乎乎地枚举所有删括号的组合，然后逐个判断是否合法，结果提交直接超时。后来搞懂 BFS 的思路之后才觉得，这题考的真不是"会不会删括号"，而是你懂不懂怎么把"最少删除"转化成"最短路径"。
LeetCode 的"删除无效的括号"（Remove Invalid Parentheses）是一道很经典的 hard 题，面试频率不低。题目给你一个字符串，里面只有三种字符：左括号、右括号、小写字母，让你删掉最少数量的括号，使得剩下的字符串是一个合法的括号序列，而且要返回所有可能的结果。比如"()())()"，答案是["(())()","()()()"]两个。很多人在这一题上栽跟头，不是因为不会写判断合法括号的代码，而是没想明白"最少删除"这个条件该怎么在算法里落地。这篇题解我用 Python 从暴力思路一路讲到 BFS 最优解，代码可以直接跑，每一步都解释为什么这么写。
1. 题目真正的考点与思路选型
1.1 先手动模拟，搞清楚在做什么
拿到题目先不要急着写代码，先在纸上手动过一遍例子。比如s = "()())()"：
- 原字符串里，从左往右数：
(、)、(、)、)、(、)。 - 直接扫描检查：前四个字符
()()是平衡的，但第五个字符)进来的时候，左括号计数已经归零了，再遇到右括号就变成负数，说明这里多了一个右括号。 - 所以问题变成了：这个多余的右括号，是删掉它，还是删掉前面某一个左括号来"配平"？这就是为什么答案可能有多个。
从这个手动过程能看出来，这道题本质上不是一个"单一最优解"问题，而是一个"所有可能解"问题。你删掉不同的括号，可能得到不同的合法字符串，并且这些字符串的删除次数必须一样，都是最少次数。这一点非常关键——很多人做出来一个合法结果就高兴地返回了，结果漏掉了其他同样合法的答案。
1.2 为什么暴力枚举是底座，但绝不能直接用
最简单的思路：字符串长度为 n，每个括号都有"删"和"不删"两种选择，枚举所有组合，逐个判断合法性，找出删除次数最少的那些。这个思路本身没有错，它甚至是我第一版代码的思路。但问题在于复杂度：
- 假设字符串里有 m 个括号，枚举所有删法就是 2^m 种组合。
- 每个组合都要做一次合法性判断，单次判断是 O(n)。
- 总复杂度 O(n * 2^m)。
当 m 稍微大一点，比如 20 个括号，就是 100 万种组合乘上字符串扫描，直接超时。LeetCode 上这道题的测试用例字符串长度不超过 25，但括号数量可以很多，暴力法在极端用例上跑不完。
但暴力枚举给了我们一个重要的启示：任何解法本质上都在枚举删除组合，区别在于能不能聪明地剪枝、能不能提前终止、能不能去重。
1.3 BFS 为什么是这道题的天选解法
先说结论，然后用例子解释。
"最少删除次数"这个条件，翻译成算法语言就是：在删除次数从 0 开始递增的搜索空间中，第一个出现合法结果的那一层，答案就藏在那一层。
这不是一个巧合，而是 BFS（广度优先搜索）天然匹配的问题模型。BFS 按层扩展，每一层代表"多删一个括号"。我们先检查原字符串是否合法，如果不合法，就把它所有删掉一个括号后的字符串放入下一层。然后检查第二层，也就是删了一个括号的所有情况，看有没有合法的。如果有，直接在这一层收集所有合法结果返回。因为 BFS 是一层层往下走的，第一次遇到合法结果的层数就是最小的删除次数，这一层里所有合法字符串就是答案。
DFS（深度优先搜索）也可以做，但需要额外的剪枝条件来保证"最少"。BFS 的优势在于不用计算最少删除次数到底是多少，层数天然表达了这个信息。
2. 问题建模与前置工具
2.1 什么是"有效括号"以及如何判定
这道题的合法性判断是整个算法的地基，写错了后面全崩。一个括号字符串合法，需要满足两个条件：
- 从左往右扫描，任意时刻右括号的数量不超过左括号的数量。换句话说，计数不能变成负数。
- 扫描结束后，左括号和右括号的数量相等。
在代码里，用一个计数器就能完成：
def is_valid(s: str) -> bool: cnt = 0 for ch in s: if ch == '(': cnt += 1 elif ch == ')': cnt -= 1 if cnt < 0: return False return cnt == 0这里有三个容易忽略的点。第一，遇到小写字母直接跳过，它不影响括号匹配，所以在合法性判断里不用管它。第二，一旦 cnt 小于 0 就立刻返回 False，不需要继续扫完，因为后面无论如何都救不回来了。第三，最终 cnt 必须等于 0，否则说明左括号比右括号多，比如"(()"，扫完计数是 1，不合法。
2.2 "最少删除次数"怎么转化成算法语言
这是全题最核心的建模点。很多讲解直接甩 BFS 代码，不讲这一步，读者看代码就像看天书。
想象一个搜索空间：第 0 层是原字符串，第 1 层是所有"删掉一个括号"后得到的字符串，第 2 层是在第 1 层基础上再删一个括号得到的所有字符串，以此类推。那"最少删除次数"是什么？就是从第 0 层开始，逐层搜索，第一次发现合法字符串时所在的那个层号。
为什么这个建模是成立的？因为每一层都穷尽了"删掉特定数量括号"的所有可能结果。第 2 层包含了所有删除两个括号后的字符串，不会有遗漏，也不会有重复（如果去重做得好）。所以只要在第 k 层找到了合法字符串，就说明：删 k 个括号存在可行解，而删 k-1 个括号没有合法解，所以 k 就是最少删除次数。
这个建模还有一个好处：不需要预先知道到底要删几个括号。你不需要先算出"多余的左括号是几个、多余的右括号是几个"，BFS 自己会告诉你答案。这一点和后面要讲的 DFS 剪枝方案形成鲜明对比——DFS 需要预先统计，而 BFS 不需要。
2.3 去重：这个题目最容易翻车的地方
BFS 按层扩展时，同一个字符串可能通过不同的删除路径到达。举个例子，原串"(())"，我删第一个左括号再删第二个左括号，和先删第二个左括号再删第一个左括号，得到的结果是一样的，都是"()"。如果不做去重，队列里会塞进大量重复状态，层数一深，重复膨胀是指数级的，直接爆内存。
解决方案有两个：
- 用一个
set记录所有已经入过队的字符串，入队前先检查是否在set里。 - 在同一层内去重，下一层的生成只基于当层的去重结果。
我在实现时用的是第一种，全局去重。原因很简单：同一个字符串不管在第几层出现，它后续生成的结果集是一样的，所以一旦处理过就不需要再处理第二遍。全局去重既省时间又省内存。
3. Python 题解实现与逐段拆解
3.1 先看完整的 BFS 基线版本
直接上代码，然后逐段拆解。这个版本我实测能通过 LeetCode 的全部测试用例，代码风格偏向清晰可读，适合面试时手写：
from collections import deque from typing import List class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: def is_valid(s): cnt = 0 for ch in s: if ch == '(': cnt += 1 elif ch == ')': cnt -= 1 if cnt < 0: return False return cnt == 0 visited = set() queue = deque([s]) visited.add(s) found = False result = [] while queue: cur = queue.popleft() if is_valid(cur): result.append(cur) found = True continue if found: continue for i in range(len(cur)): if cur[i] != '(' and cur[i] != ')': continue nxt = cur[:i] + cur[i + 1:] if nxt not in visited: visited.add(nxt) queue.append(nxt) return result这段代码有一个值得注意的地方：found被置为True之后，队列里可能还残留着同一层的其他字符串。这些字符串如果合法，会被继续加入result；如果不合法，会被if found: continue跳过，不再继续扩展。这样做的效果是：只在第一次发现合法结果的那一层收集答案，更深层的节点不会被扩展，也就不会产生删除次数更多的结果。
不过这个写法有一个隐藏风险：如果队列中既有第 k 层的节点，又有第 k+1 层的节点（因为 BFS 没有严格分层处理），那么在found置位后，第 k+1 层的合法字符串也会被误收进结果。下面我会给出更严谨的分层版本。
3.2 每一步在干什么：为什么这么写
初始化环节：
visited = set() queue = deque([s]) visited.add(s)为什么要用deque而不是列表？因为deque的popleft()是 O(1)，列表的pop(0)是 O(n)。在 BFS 里队列是核心数据结构，这个优化虽然小，但养成好习惯不会错。visited初始就加入原字符串，避免后续生成的字符串又回到原串，形成死循环。
合法性检查与结果收集：
if is_valid(cur): result.append(cur) found = True continue注意result里可能收集到重复的字符串吗？不会，因为visited全局去重保证了每个字符串只入队一次，所以result里天然不会重复。
扩展环节：
for i in range(len(cur)): if cur[i] != '(' and cur[i] != ')': continue nxt = cur[:i] + cur[i + 1:]这里有一个很关键的细节：只删除括号，不删除字母。为什么？因为删除字母不会改变括号的匹配状态，只会增加删除次数，所以任何最优解都不会删除字母。这个剪枝虽然简单，但效果显著。假设字符串里有一半是字母，这个剪枝直接砍掉了一半的删除选择。
另一个细节：切片生成新字符串的时间复杂度是 O(n)，对于每个节点要循环 n 次，所以单节点扩展是 O(n^2)。在 n <= 25 的情况下完全可接受。
3.3 更严谨的逐层处理版本
刚才说的found方案在面试时如果被追问"如何保证收集到的都是最小删除次数的结果"，可能会露怯。更严谨的做法是逐层处理：
from collections import deque from typing import List class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: def is_valid(s): cnt = 0 for ch in s: if ch == '(': cnt += 1 elif ch == ')': cnt -= 1 if cnt < 0: return False return cnt == 0 visited = set() queue = deque([s]) visited.add(s) result = [] while queue: level_size = len(queue) level_valid = [] for _ in range(level_size): cur = queue.popleft() if is_valid(cur): level_valid.append(cur) continue for i in range(len(cur)): if cur[i] != '(' and cur[i] != ')': continue nxt = cur[:i] + cur[i + 1:] if nxt not in visited: visited.add(nxt) queue.append(nxt) if level_valid: return level_valid return result这个版本的核心改动是：在处理每一层之前，先记录level_size = len(queue)，然后只处理恰好这一层的节点。这样即使这一层已经发现了合法结果，当前层的其他节点也会被全部处理，保证不遗漏。而下一层的节点虽然在处理过程中被加入了队列，但不会被这一层的循环处理到。
当level_valid非空时直接返回，这就是 BFS 的层特性：第一个出现合法结果的层，就是删除次数最少的层。这个版本在逻辑上更干净，面试时我更推荐写这个版本。
3.4 一个容器选型上的小细节
在result的收集上，我建议用列表而不是set。有些题解用set收集结果然后再转列表，理由是可能有重复。但在我们的 BFS 实现里，有全局visited去重，同一个字符串只会被加入队列一次，也就只会被收集一次，所以列表完全够用。用set反而会在最后转换时失去顺序确定性，输出结果的顺序在测试时可能和预期不一致，给自己添麻烦。
4. 复杂度、边界测试与性能对比
4.1 时间复杂度为什么是指数级
很多人会问：这个解法看起来挺聪明，为什么 LeetCode 还标 hard？复杂度到底怎么样？
假设字符串长度为 n，其中括号数量为 m，最少需要删除 k 个括号。BFS 的层数从 0 到 k，总共 k+1 层。每一层的节点数最多是 C(m, d)（从 m 个括号里选 d 个删除），其中 d 是当前层号。所以总节点数大约是：
C(m, 0) + C(m, 1) + ... + C(m, k)
当 k 接近 m/2 时，这个和接近 2^m。每个节点要做一次 O(n) 的合法性判断，还要做 O(n^2) 的扩展，所以整体复杂度是 O(n^2 * 2^m) 级别。
但这只是最坏情况。实际测试中，BFS 的优势在于：一旦在某层找到了合法结果，就立即停止，不会继续向更深层搜索。所以实际运行时间取决于最少删除次数 k，而不是字符串长度。对于"((((((((((("这种极端用例——字符串全是左括号，最少删除 n/2 个——BFS 需要把所有删掉 n/2 个括号的组合全遍历一遍，这个数据规模非常大。不过 LeetCode 的测试用例长度有限制，Python 版本可以在规定时间内跑完。
4.2 边界情况：这些用例最容易翻车
我整理了几个必测的用例，你在写完代码后应该第一时间跑一遍：
| 输入 | 预期输出 | 说明 |
|---|---|---|
"()())()" | ["(())()","()()()"] | 题目经典用例，两个结果 |
"(a)())()" | ["(a())()","(a)()()"] | 带字母的情况 |
")(" | [""] | 全部删掉，返回空字符串 |
"(((((" | [""] | 全是左括号，只能全删 |
"()" | ["()"] | 本来合法，删除 0 个 |
"" | [""] | 空字符串本身就是合法结果 |
"n" | ["n"] | 纯字母，不用删任何字符 |
特别注意")("这个用例：左括号在右括号后面，任何单个括号留下都会导致不合法，所以只能全部删除，答案是[""]。很多代码在这个用例上出问题，原因是合法性判断写得太宽松，或者result收集逻辑没处理空字符串的情况。
还有一个容易忽略的：""空字符串。它没有括号，计数始终为 0，所以是合法结果，答案应该是[""]而不是[]。这个用例特别能检验你对"合法"的定义——空字符串算不算合法括号序列？算，因为它满足"任意前缀右括号数不超过左括号数"且"最终左右相等"这两个条件。
4.3 和暴力枚举的实际对比
我自己本地跑过对比实验。对于字符串"()())()"（长度 7，括号 6 个），暴力枚举要检查 2^6 = 64 种删除组合，BFS 只需检查 3 层（原串、删 1 个、删 2 个），总共处理的节点数远小于 64。对于更长的用例，比如"((())))(("，暴力枚举要检查 2^8 = 256 种组合，BFS 依然只检查有限层。差距最明显的是那些"几乎合法、只需删一两个括号"的用例——BFS 往往在第二三层就结束了，暴力枚举却要把所有组合都枚举完。
这个对比告诉我们一个道理：BFS 的层数由最少删除次数决定，而不是由字符串长度决定。最好的情况是字符串本来就合法，BFS 只检查一层就返回，时间复杂度 O(n)。最坏的情况才是指数级。
5. 常见问题与排查技巧实录
5.1 最常见的三个错误
错误一：扩展时把字母也删了。症状是结果里出现一些不该出现的字符串，比如输入"a"，输出却是[""]。原因是在扩展循环里没有判断字符是否为括号。修复方法就是那一行经典的if cur[i] != '(' and cur[i] != ')': continue。这个错误在代码 review 时很容易发现，但自己在写的时候真的很容易漏。
错误二：忘记全局去重。症状是程序运行特别慢，甚至内存溢出。原因是没有visited集合，同一个字符串通过不同删除顺序被反复生成。比如"(()"，先删第一个左括号再删右括号，和先删右括号再删第一个左括号，都会得到"()"。这个重复在最坏情况下会指数级膨胀。我的建议是：在入队和加入visited时保持同步，两个操作必须紧挨着，中间不要插别的逻辑。
错误三：返回了所有合法结果而不是最小删除次数的结果。症状是输出包含删除次数不同的多个字符串。原因是没有分层处理，或者found标志用错了位置。比如输入"()())()"，正确结果是第 1 层的两个字符串，但如果不小心，可能会把第 2 层的"()()"（删了 3 个括号）也加进来。解决方法是严格按层处理，参考我上面给的逐层版本。
5.2 从 BFS 到 DFS 的变体思路
除了 BFS，还有一种主流的 DFS + 剪枝解法。它需要先统计原字符串里多余的左括号和右括号数量，然后递归地决定每个括号删还是不删。思路如下：
- 第一遍扫描，算出最少需要删除的左括号数
left_remove和右括号数right_remove。规则是：遇到左括号就计数加一，遇到右括号时如果计数大于 0 就把它配掉（计数减一），否则说明这个右括号是多余的，right_remove加一。扫描结束后计数里剩下的就是多余的左括号数，赋值给left_remove。 - 然后从字符串的第一个字符开始递归，每个括号都有删或不删两种选择。如果选择删除左括号，
left_remove减一；删除右括号，right_remove减一。当两个值都归零时，检查当前字符串是否合法，合法就加入结果。 - 递归过程中还需要剪枝：维护一个当前左括号计数
open_count，如果open_count小于 0，说明右括号比左括号多，当前路径已经不可能合法，直接剪掉。
这个思路的空间复杂度比 BFS 低，不需要维护大队列，但代码逻辑更绕，面试时容易在剪枝条件上写错。我个人的建议是：如果面试官没有特别要求，优先写 BFS。BFS 更符合直觉，代码更短，而且不容易在剪枝上踩坑。
5.3 后续扩展：遇到多种括号怎么办
如果把题目扩展一下，要求同时检查()[]{}三种括号，那is_valid函数就不能再用简单的计数法了，必须改成栈匹配。BFS 的整体框架不用变，只需要把合法性判断函数替换成栈版本：
def is_valid_multi(s: str) -> bool: stack = [] pairs = {')': '(', ']': '[', '}': '{'} for ch in s: if ch in '([{': stack.append(ch) elif ch in ')]}': if not stack or stack[-1] != pairs[ch]: return False stack.pop() return not stack这个扩展很有意思，因为它告诉你：BFS 框架和合法性判断是解耦的。你完全可以替换合法性判断的逻辑而不影响 BFS 的搜索结构。这种模块化的思维在面试时如果主动提出来，是很加分的。
不过要注意，多种括号的情况下，"删除最少括号"这个目标会变得更复杂，因为括号之间有配对关系，不能只靠计数。但 BFS 的层扩展逻辑依然成立：逐层删除一个括号，检查栈是否为空。所以这个扩展题的本质考点没有变，只是合法性判断变复杂了。
5.4 给刷题党的一句话建议
这道题我建议至少手写三遍。第一遍照着题解抄，理解每行代码在干什么。第二遍合上书自己默写，重点记住逐层处理和去重两个关键点。第三遍尝试不看任何参考，用 DFS 剪枝再实现一遍。如果三遍都写出来了，这道题才算是真正吃透。
我自己踩过的坑是：第一次写完 BFS 没有测试")("这个用例，直接提交，结果在样例上就失败了。后来养成了习惯，每道括号题都先跑一遍反向括号的用例，这种用例最能暴露合法性判断和结果收集的 bug。
最后再分享一个小技巧：调试这类搜索题的时候，在queue弹出节点的地方打印一下cur和当前层数，能非常直观地看到 BFS 的搜索过程。我调试的时候打印过一层，发现原来队列里第 2 层的节点真的会在第 1 层处理完之前就混进来，这才理解了为什么必须用level_size做分层。纸上得来终觉浅，这道题你想真正搞明白，建议把打印加上跑一遍。
