先说结论这道题我在不同阶段的解法完全不一样。第一次做的时候我傻乎乎地枚举所有删括号的组合然后逐个判断是否合法结果提交直接超时。后来搞懂 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 层的节点又有第 k1 层的节点因为 BFS 没有严格分层处理那么在found置位后第 k1 层的合法字符串也会被误收进结果。下面我会给出更严谨的分层版本。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总共 k1 层。每一层的节点数最多是 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做分层。纸上得来终觉浅这道题你想真正搞明白建议把打印加上跑一遍。