刷题刷到中后期判断一道题有没有嚼头我习惯先看它能不能一句话问懵人。删除无效的括号就是这么一道题看起来只是把字符串里多余的括号删掉但真要动手写才发现必须回答三个问题——删几个、删哪些、重复结果怎么办。这道题在各类算法题库里都非常经典也是面试环节的常客它表面考回溯实际考的是对括号匹配本质的理解程度。这篇题解我会用 Python 把这道题拆开讲透先用计数器算清最少要删多少括号再讲 DFS 回溯如何枚举所有方案最后补充 BFS 版本和几处很容易翻车的边界细节。1. 括号问题的底层规律合法括号串不能只靠数量相等很多人拿到这道题的第一反应是统计字符串里左右括号的数量哪边多就删哪边删到一样多不就合法了吗这个思路对了一半但如果真按这个逻辑写会挂在下面这个例子上。1.1 一个反直觉的例子)(( 左右括号数量相等却完全非法先看字符串)((。它有两个右括号不对准确说是)(这个例子更典型但我们可以用一个更极端的)((有两个左括号一个右括号我重新选个干净的例子)(。左右括号各一个数量相等但显然不合法因为第一个字符就是右括号它没法和任何左侧的左括号配对。再比如))((左右各两个数量完全相等但整个串里没有一对合法括号。这类字符串的存在说明括号合法性的判定条件和数量相等是两回事。1.2 判定合法只需要一个计数器判断一个括号串是否合法不需要栈也不需要正则一个整数计数器就够了。我从左往右扫描整个字符串维护一个变量balance规则只有两条遇到左括号(balance 1遇到右括号)balance - 1如果减完之后balance 0立刻判定非法。扫描结束后balance必须恰好等于 0这个字符串才合法。这个规则背后的直觉很生活化把左括号想象成欠条右括号想象成还款。你可以在任何时刻持有欠条balance 为正但绝不能在没欠条的时候还款balance 变成负数。扫描结束还欠着钱balance 为正也不行因为字符串已经结束了没人再给你还款机会。所以删除无效的括号这道题本质上就是在保证balance全程不为负、最终为 0 的前提下用最少的删除次数改造原串。理解了这个计数器逻辑后面所有的解法都建立在这条规则之上。2. 先算最少删几个预扫描给出删除配额暴力做法是枚举所有子序列再逐个判断合法性。但s最长能有 25 个字符子序列数量是 2 的 25 次方也就是三千多万每个还要做一次线性合法性校验Python 直接跑会非常吃力。所以正确姿势是先做一次预处理算出最少必须删除的左括号数和最少必须删除的右括号数把问题从删多少个缩小为删哪几个。2.1 预扫描规则与手算演示我用两个变量lrem和rrem分别记录需要删除的左括号数、右括号数从左往右扫描原串遇到左括号lrem 1意思是当前有一个左括号等待被匹配遇到右括号先看lrem是否大于 0。如果大于 0说明这个右括号能匹配掉前面一个还没配对的左括号让lrem - 1如果lrem已经是 0说明这个右括号前面没有可匹配的左括号它本身是多余的必须删掉所以rrem 1。扫描结束后lrem里剩下的就是到末尾都没被匹配掉的左括号也是必须删除的rrem就是必须删除的右括号。拿题目给的示例s ()())()走一遍字符操作前 lrem操作前 rrem操作后 lrem操作后 rrem(0010)1000(0010)1000)0001(0111)1101结果lrem 0rrem 1。也就是说这个字符串只需要删除 1 个右括号就能变合法这和题目的预期输出完全对得上[(())(), ()()()]都是删除一个右括号后的结果。2.2 为什么最优解必然刚好删掉这些配额这个预扫描为什么可信因为它是贪心的。它对每个右括号做的是能匹配就匹配这意味着所有能被正常匹配的括号都消耗掉了剩下的左括号和右括号本质上就是结构性冗余。关键结论是任何一组删除最少数量括号后合法的解删掉的左括号数量必然等于lrem删掉的右括号数量必然等于rrem。理由很简单——预扫描找出的这些括号是必须删的因为不删它们就不可能让 balance 归零且不为负而如果删了别的括号删除总数就会超过最小值。所以最优解恰好拥有固定的删除配额我们后面枚举的只是配额内部的分配方案。2.3 配额如何变成剪枝条件有了配额递归时的剪枝条件就很清晰了在当前分支里如果已经删除的左括号数超过lrem或者删除的右括号数超过rrem这个分支就已经偏离最优解直接终止。这一步能把大量无效分支提前掐死是 DFS 版本性能的关键。3. DFS 主解逐字符决策 剪枝 去重预处理拿到删除配额后核心问题就变成从字符串的每个位置开始决定这个字符是保留还是删除。因为我们已经知道最多删多少个括号所以这不是无边无际的搜索而是在一个很小的解空间里找所有方案。3.1 递归的状态设计与转移条件我设计递归函数时每个参数都要有意义pos当前扫描到原串s的哪个位置cur已经构造出来的前缀字符串balance当前前缀里未匹配的左括号数量lrem/rrem剩余还能删除的左括号数、右括号数。每来到一个字符只有三种情况当前字符是普通字母普通字母不在删除范围内直接保留cur后追加这个字母其他状态不变。当前字符是左括号要么保留balance 1要么删除lrem - 1。当前字符是右括号要么删除rrem - 1要么保留。但保留右括号有一个前提条件当前balance必须大于 0。因为如果前面没有未匹配的左括号这个右括号一保留balance 立刻变负数后续就算把整个字符串走完也不可能修复了。这个保留右括号前检查 balance的剪枝是整棵树能不能瘦身的关键。没有它递归会在大量注定非法的分支里白跑。递归终止条件pos扫描完了同时balance 0且lrem 0且rrem 0这个cur就是一个合法答案。3.2 完整 Python 实现from typing import List class Solution: def removeInvalidParentheses(self, s: str) - List[str]: # 第一次扫描统计最少需要删除的左、右括号数量 lrem rrem 0 for ch in s: if ch (: lrem 1 elif ch ): if lrem 0: lrem - 1 else: rrem 1 ans [] visited set() n len(s) def dfs(pos: int, cur: str, balance: int, lrem: int, rrem: int) - None: if balance 0 or lrem 0 or rrem 0: return key (pos, cur, balance, lrem, rrem) if key in visited: return visited.add(key) if pos n: if balance 0 and lrem 0 and rrem 0: ans.append(cur) return ch s[pos] if ch (: # 删掉这个左括号 if lrem 0: dfs(pos 1, cur, balance, lrem - 1, rrem) # 保留这个左括号 dfs(pos 1, cur ch, balance 1, lrem, rrem) elif ch ): # 删掉这个右括号 if rrem 0: dfs(pos 1, cur, balance, lrem, rrem - 1) # 保留右括号前面必须有未匹配的左括号 if balance 0: dfs(pos 1, cur ch, balance - 1, lrem, rrem) else: # 普通字母只能保留 dfs(pos 1, cur ch, balance, lrem, rrem) dfs(0, , 0, lrem, rrem) return ans这份代码直接提交就能通过。它在每个位置都走删和不删两条路但因为配额和 balance 的双重剪枝实际展开的分支数远小于 2 的 N 次方。3.3 为什么需要 visited 去重如果字符串里有多个连续的相同括号比如((a删除第一个左括号和删除第二个左括号最终得到的都是(a。DFS 会把这两条不同路径都走到尽头产生同一个结果。我没用最后对结果去重这种偷懒方案而是在状态层面去重。只要(pos, cur, balance, lrem, rrem)完全一致后续无论怎么走都等价只搜一次就够了。这个细节对性能影响非常大尤其当输入里有连续重复括号序列时能省下很多重复分支。4. BFS 备选方案按层删除的直观思路DFS 是先算配额再搜索BFS 则是另一种完全不同的思路从原串开始每一层尝试删除一个括号生成所有可能的新字符串直到这一层出现了合法字符串。因为 BFS 是按删除次数一层层扩展的所以第一次遇到合法串的那一层就是最少删除次数。4.1 BFS 版本 Python 实现from collections import deque from typing import List class Solution: def removeInvalidParentheses(self, s: str) - List[str]: def is_valid(x: str) - bool: balance 0 for ch in x: if ch (: balance 1 elif ch ): balance - 1 if balance 0: return False return balance 0 visited {s} q deque([s]) ans [] found False while q: cur q.popleft() if is_valid(cur): ans.append(cur) found True continue if found: # 已经找到最少删除次数的结果不再继续生成更短的串 continue for i, ch in enumerate(cur): if ch not in (): continue nxt cur[:i] cur[i 1:] if nxt not in visited: visited.add(nxt) q.append(nxt) return ans这里有个容易写错的地方found True之后当前队列里可能还有其他字符串它们和已经找到的合法串处于同一删除层也必须处理。所以我在is_valid(cur)为真时先收集答案、再continue只有对非法的cur才用if found跳过扩展。这样才能保证把所有同层合法结果都收集全。4.2 两种解法的取舍复杂度不是唯一指标BFS 的时间复杂度理论上也是 O(2^N * N)空间复杂度 O(2^N * N)看起来和 DFS 差不多但它有个明显的短板如果原串需要删除的括号数很大BFS 要一层一层删下去遍历大量中间字符串。比如输入是一长串(((((((((((((((((((((((((BFS 要删到第 25 层才能得到空串这个合法结果中间产生的所有中间串都要被生成和判重非常浪费。DFS 版本的预扫描会直接告诉它必须删掉 25 个左括号于是一路删到底几乎没有无效分支。所以我个人推荐默认用 DFS 版本它的剪枝信息更充分代码也更紧凑。BFS 的优势是思考成本低不需要先理解配额这个概念只要懂层级遍历就能写出来。如果是在面试里可以先用 BFS 的思路和面试官对齐按层扩展的直觉再手写 DFS 做最终实现。5. 边界情况与隐藏的坑实测中容易翻车的地方这道题代码量不大但边界情况相当多。我在实际调试和给别人 review 代码时见过不少次逻辑看着对一提交就报错的案例下面这几个是最值得注意的。5.1 常规边界用例速查表输入预期输出说明[]空串本身合法a[a]不含括号原样返回([]必须删掉唯一的左括号)([]两个括号都不匹配()[()]本来就合法不能多删((((((((((((((((((((((((([]全左括号只能全删(a)())()[(a())(), (a)()()]普通字母混在中间也要正确处理全左括号这种用例最容易测出问题。如果递归里没有balance 0的最终校验或者扫描配额算错就会把(、((这些中间态也当成答案输出。5.2 连续重复括号导致的重复答案前面说过 visited 去重的作用。这里再具体演示一个容易踩的坑s ((a。它的合法结果只有(a一个但如果不做任何去重DFS 会从删第 1 个左括号和删第 2 个左括号两条路各走过一次结果ans里出现两个(a。题目要求返回不重复的结果集合所以这个去重是必须的。如果你想验证自己的实现有没有踩这个坑我建议直接用包含连续同种括号的用例去测比如((((a))))。这个输入会产生非常多的重复路径是去重逻辑的照妖镜。5.3 递归深度与队列性能Python 递归深度默认是 1000而题目字符串长度上限只有 25递归深度完全不用担心。但要注意如果在本地测试时把字符串长度改到几百上千DFS 版本就可能触发递归深度限制那就要考虑改成显式栈了。BFS 版本里我用了collections.deque而不是list.pop(0)。list.pop(0)的时间复杂度是 O(N)每次弹出都要把后面所有元素前移在字符串数量多的时候会拖慢整体速度。deque.popleft()是 O(1)刷题时这种实现细节能省一部分运行时间。6. 从这道题延伸出的通用套路刷题不能只背答案。这道题表面上是个回溯题但它背后的方法论可以复用到很多别的题目上。6.1 先定配额再枚举方案的解题模板这个套路分三步用一次贪心扫描确定必须操作的上限比如这里是最少删除的左右括号数把删除问题改写成逐字符的取舍问题递归或者循环里既考虑删也考虑不删用状态去重 合法性剪枝把无效分支提前砍掉。这套模板不只是括号题能用。比如字符串转有效 IP 地址、复原各种被分隔符切碎的原始串本质上都是先确定必须填充/删除的量再枚举所有组合。遇到这类题目先想想能不能把无限枚举压缩成有限决策。6.2 相关变式题的对比题目方向核心思路和本题的关联括号生成回溯生成所有合法括号对平衡balance的规则完全一样最长有效括号栈或动态规划记的是括号之间的匹配关系最少添加使括号有效贪心扫描本题的预扫描就是它的答案判断括号是否有效计数器或栈本题的合法性校验函数我自己的体会是如果能把删除无效的括号的预扫描逻辑吃透那最少添加那类题基本就是白送。因为预扫描得到的lrem rrem恰恰就是最少需要添加的括号数量连代码都不用怎么改。最后说一点个人经验。我最初做这道题的时候第一版写的是纯暴力枚举所有子序列结果跑到(((((((((())))))))))这种用例直接卡死。后来才意识到回溯题的复杂度瓶颈往往不在枚举本身而在于怎么证明自己枚举得足够少。预扫描算配额这一步就是把指数级问题缩减到只枚举最少数量的删除方案的关键。如果你在面试中遇到类似的字符串回溯题不妨先别急着写递归花三十秒把那个贪心扫描写好后面的代码会顺畅很多。这道题刷完之后建议自己动手把 DFS 和 BFS 两个版本各写三遍直到能闭眼还原等写熟了你会发现很多括号相关的变体题都不再是难题了。