LeetCode 678 这道题我印象里至少有不下三波同学问过我同一个问题为什么题解看懂了自己一写还是错这道题在题库里叫Valid Parenthesis String中文社区一般翻译成“有效的括号字符串”属于括号匹配这个经典序列里综合难度相当高的一档。它和普通的“有效的括号”最大区别是引入了字符*这玩意既能当左括号、也能当右括号、还能什么都不当一下就把“判定一个序列是否合法”变成了“判定一堆字符有没有可能凑成合法序列”。对准备面试的人来说这题经常出现在某书的栈与贪心专题里也是 LeetCode 热门 100 题的常客对口试算法基础的人来说它又是很好的思维试金石——刷过这题你再回去看 20、22、32 这些括号题整个体系都会通透很多。1. 题目拆解一个星号把括号匹配从确定变成可能1.1 题目到底在说什么三个字符的博弈先看题目本身。给定一个字符串只包含三类字符(、)和*。你需要判断这个字符串是否可能是一个有效的括号字符串。有效括号串的定义延续了 LeetCode 20 题的经典定义左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合空字符串视为有效。难点全在那个*上。它有三个身份作为空字符串什么都不贡献作为左括号(增加一个未匹配左括号作为右括号)减少一个未匹配左括号。举个例子字符串(*)是有效的因为*可以当作空串得到()也可以把*当作左括号得到(()不对(()是不合法的所以这个例子里*只能充当空串。再看(*))这个也有效把*当作(字符串变成(())完全合法。单个*也有效它可以当作空串。这就意味着我们不能像 20 题一样只维护一个“当前未匹配左括号数”的变量因为*的存在让这个数字不再唯一。它可能比我们看到的少也可能比我们看到的多。题目问的是“是否存在某一种对*的赋值使得整个串合法”而不是“所有可能里任一一种成立就行”。准确说只要存在一种就行所以我们反而要找的是最大可能和最小可能。1.2 最容易踩的审题陷阱*不是正则里的通配符我见过不少同学第一眼就把*当成正则通配符觉得它能匹配任意字符、任意长度。这题里的*没有“匹配任意字符”的语义它只能被解释成三种状态之一而且每个*选择是独立的。更重要的一点是它不能“既当左括号又当右括号”同一个*在同一时刻只能选一种身份但不同*可以选不同身份。还有一个很容易忽略的前提有效括号要求“按正确的顺序闭合”。也就是说用*充当右括号去匹配一个左括号时这个*必须出现在左括号之后反过来用*充当左括号去匹配右括号时星号要出现在右括号之前。顺序性是这个题能解的根基也是后面双栈解法里必须比较下标的原因。如果忽略顺序你会以为*(是合法的其实它不是——星号如果充当右括号它后面没有任何左括号可匹配如果充当左括号或空串字符串就变成(或(?反正会剩一个左括号不合法。1.3 暴力穷举为什么不可行最简单的思路是把每个*枚举成三种状态最后检查所有可能的字符串里有没有一个是合法括号串。字符*数量为 k 时复杂度是 O(3^k)。LeetCode 的测试用例里字符串长度上限是 100这意味着 k 最多到 1003^100 这个数字比宇宙中的原子数还夸张显然不可能。暴力的价值只是帮助我们确认一个直觉这题本质是个搜索问题只是在搜索空间里寻找“有没有一条路径能走到合法状态”所以可以用区间、栈、动态规划等方法去压缩这个搜索空间。背后真正的考点就两件事第一你能不能把“可能性”建模成一段连续区间第二你懂不懂用栈去保留顺序信息。下面我按三种主流解法一个一个拆开讲。2. 贪心双变量法把左括号余额当成一段水位区间2.1 核心直觉平衡不是一个点而是一个区间这题最经典的解法是贪心双变量我建议把它当成首选方案掌握。思路只有一句话不要维护一个精确的“当前未匹配左括号数量”而是维护这个数量的最小可能值和最大可能值。用生活类比解释一下。想象你在一栋楼里一层一层往下走左括号是向上走一层右括号是向下走一层*是一块既能当上行扶梯又能当下行扶梯的神奇踏板。普通情况下你只有一个精确楼层有*时你其实站在一个高度区间里——最低可能到哪一层最高可能到哪一层只要区间里包含 0也就是最终回到地面就说明存在一条合法路径。定义两个变量lo当前未匹配左括号数量的最小值也就是把每个*都尽可能当作右括号或空串时剩下最少会有多少个左括号没被匹配。hi当前未匹配左括号数量的最大值也就是把每个*都尽可能当作左括号时最多会积压多少个左括号。我们的目标是走完整个字符串后lo能回到 0同时任何时刻hi不能小于 0。为什么只要看lo能不能回到 0因为只有lo 0才表示存在一种解释让所有左括号都能被匹配掉。你可能觉得应该看区间是否包含 0而lo就是区间下界hi是上界区间包含 0 当且仅当下界lo 0。由于lo被强制归零过下面解释所以最终只需判断lo 0。2.2 三种字符如何推动区间变化逐个字符扫描规则如下。遇到(这是一个确定的左括号所以不管怎么解释未匹配左括号数量都会加 1。因此lohi。遇到)这是一个确定的右括号无论前面怎么解释它都要消耗一个左括号。所以lo--hi--。这里要立刻做两件事如果hi 0说明即使把前面所有*都当成左括号也凑不够当前这个右括号需要的左括号数整个串不可能合法直接返回 false。同时lo如果小于 0说明哪怕把所有*都当作空串当前还是多出右括号因为右括号不能放在左括号之前匹配多出的右括号没有意义这时把lo归零即可。遇到*它可以是左括号、右括号或空串。所以区间会发生三种变化当右括号时lo--当左括号时hi当空串时不变。合起来的效果是lo--、hi。也就是说区间整体往下扩一圈、往上扩一圈区间宽度变大。处理完同样要检查lo是否小于 0若是则归零再检查hi是否小于 0。最后遍历完如果lo 0返回 true否则返回 false。因为lo代表最少剩余左括号数如果它都大于 0说明即使在所有*都充当右括号的情况下左括号仍然过剩无法合法。这里有一个细节需要理解透彻为什么lo小于 0 时直接归零而不是继续负数累积因为负的lo代表的是“到目前为止右括号比左括号多”的差值而在括号匹配问题里右括号一旦出现就必须立刻有左括号来匹配不能留到后面。如果中间出现lo为负说明某些右括号没有对应的左括号这种解释路径已经死了。但我们只需要保留那些“仍然可能走向合法”的解释所以把下界重新钳制回 0表示“当前最乐观情况下未匹配左括号数最少是 0”。2.3 代码实现Python 与 Java 双版本直接看代码Python 版本class Solution: def checkValidString(self, s: str) - bool: lo hi 0 for ch in s: if ch (: lo 1 hi 1 elif ch ): lo - 1 hi - 1 else: # * lo - 1 hi 1 if hi 0: return False lo max(lo, 0) return lo 0Java 版本长得几乎一样class Solution { public boolean checkValidString(String s) { int lo 0, hi 0; for (char c : s.toCharArray()) { if (c () { lo; hi; } else if (c )) { lo--; hi--; } else { lo--; hi; } if (hi 0) return false; lo Math.max(lo, 0); } return lo 0; } }别看代码只有十几行它把上面一堆理论全浓缩进去了。我自己第一次写的时候最容易漏的就是hi 0这个提前返回条件。如果没有它遇到)这种串hi会变成 -1最后lo也可能是 0返回 true——显然是错的。2.4 边界情况测试与复杂度说明用几个典型用例验证空串循环直接结束lo 0返回 true。*lo -1归零为 0hi 1最终lo 0返回 true。(lo 1hi 1最终lo 1返回 false。)lo -1归零hi -1hi 0直接返回 false。((*)过程不细算最终lo应该为 1返回 false。(*)最终lo为 0返回 true。(*))最终lo为 0返回 true。时间和空间复杂度都很漂亮一趟扫描O(n) 时间O(1) 空间。这也是面试里最推荐给出的方案因为写起来快解释清楚后面试官基本都能跟上。3. 双栈模拟拒绝玄学用下标来证明匹配顺序3.1 为什么栈在这种题里还能用贪心跳过了顺序这个细节只靠数字在推。但如果你在面试时想讲得更“扎实”或者面试官追问“你怎么证明存在性”双栈解法是更好的回答。普通的括号匹配问题用栈记录每个(的位置遇到)时弹栈遇到栈空则说明右括号多余。但这题多了一批可以“救火”的*它们既能顶替左括号也能顶替右括号。我们需要两个栈leftStack记录所有(的下标starStack记录所有*的下标。遇到)时优先用左括号栈来匹配如果左括号栈空了才考虑用星号栈来顶替左括号。为什么优先用左括号因为*是“万能救兵”它应该留给更麻烦的局面例如后面没有左括号可用时。这也是贪心策略在栈解法里的体现。3.2 一个案例走通全过程拿字符串(*))举例这个用例能覆盖所有分支。下标从 0 开始。i0字符(入 leftStack栈内容 [0]。i1字符*入 starStack栈内容 [1]。i2字符)leftStack 非空弹出 0匹配成功。此时 leftStack []starStack [1]。i3字符)leftStack 空starStack 非空弹出 1让这个星号充当左括号去匹配。匹配成功。遍历结束leftStack 和 starStack 都为空返回 true。再看一个非法串*(i0*入 starStack[0]。i1(入 leftStack[1]。遍历结束leftStack 非空需要用 starStack 里的星号去匹配左括号。弹出比较leftStack 弹出 1starStack 弹出 0。左括号下标 1 大于星号下标 0说明星号在左括号前面它只能充当左括号或空串不能充当右括号去匹配这个后面的左括号。返回 false。这个最后一个步骤特别关键星号如果要充当右括号它的下标必须大于左括号的下标也就是必须出现在左括号之后。栈里保存下标就是为了在这一步做大小比较。3.3 代码实现与两个必踩的坑class Solution: def checkValidString(self, s: str) - bool: left_stack [] star_stack [] for i, ch in enumerate(s): if ch (: left_stack.append(i) elif ch *: star_stack.append(i) else: # ch ) if left_stack: left_stack.pop() elif star_stack: star_stack.pop() else: return False while left_stack and star_stack: if left_stack.pop() star_stack.pop(): return False return len(left_stack) 0两个坑分别是第一遇到)时不能优先使用星号。假设星号在右括号前面一点且后续还需要星号充当左括号你提前用掉就可能导致后面无解。所以原则是先用实打实的左括号万不得已再用星号。第二收尾匹配时必须比较下标。如果省去比较*(会被错误判成合法。我见过很多次有人写的双栈代码少了这一步最后返回len(left_stack) 0看起来逻辑自洽实际上漏掉了顺序性约束。3.4 贪心和双栈面试时选哪个我的建议是写代码用贪心讲思路先讲双栈。因为双栈的每一步都对应着具体字符很容易向面试官展示“我是一个个字符处理遇到右括号优先找左括号找不到找星号”的过程。但双栈要求维护两个栈代码量略多收尾的下标比较也容易绕。贪心代码极短跑起来极快面试现场手写不容易出错。如果你想把两个都掌握熟练可以这样自我训练今天写双栈并加上注释明天默写贪心并口头解释lo、hi的含义。两天下来这道题基本就焊死在脑子里了。4. 动态规划解法把可能性铺开成一张表4.1 为什么要讲 DP它是字符串题的万能后手不是所有面试官都只想听最优解有些人会追问“还有没有别的思路”“如果字符串长度限制更小你会怎么做”。这时候 DP 就派上用场了。更重要的是LeetCode 上很多字符串匹配问题——比如通配符匹配、正则表达式匹配——思路和这题的 DP 是一脉相承的。学会 678 的 DP 写法迁移到那些题会轻松很多。DP 的思路是模拟整个扫描过程记录每一步所有可能的“未匹配左括号数量”。定义dp[i][j]表示字符串的前i个字符处理完后是否存在一种解释方式使得当前还有j个左括号没有被匹配。j的取值范围是 0 到i因为前i个字符里最多出现i个左括号所以未匹配数量不可能超过i。最终我们要看的是dp[n][0]是否为 true。4.2 状态转移三种字符三条路初始化dp[0][0] true表示空前缀、没有未匹配左括号一定可达。对于第i个字符ch从dp[i-1][j]开始转移如果ch (只能让未匹配左括号数量加 1所以dp[i][j1] true如果ch )只有j 0时才能消耗一个左括号所以dp[i][j-1] true如果ch *三种身份都允许所以空串时dp[i][j] true当左括号时dp[i][j1] true当右括号且j 0时dp[i][j-1] true。这里有一个容易出错的小地方j是从dp[i-1][j]继承过来的扫描第i个字符之前未匹配左括号数最多是i-1所以内层循环j最多枚举到i-1就足够了枚举到i只是多遍历几个必然为 false 的状态。4.3 DP 代码实现二维版与滚动数组优化先写二维版方便你对照理解class Solution: def checkValidString(self, s: str) - bool: n len(s) dp [[False] * (n 1) for _ in range(n 1)] dp[0][0] True for i in range(1, n 1): ch s[i - 1] for j in range(i): if not dp[i - 1][j]: continue if ch (: dp[i][j 1] True elif ch ): if j 0: dp[i][j - 1] True else: dp[i][j] True dp[i][j 1] True if j 0: dp[i][j - 1] True return dp[n][0]这个版本的时间复杂度是 O(n^2)空间也是 O(n^2)。明显比贪心重但胜在逻辑直白不容易漏边界。因为每一行只依赖上一行所以可以滚动数组把空间压到 O(n)class Solution: def checkValidString(self, s: str) - bool: n len(s) dp [False] * (n 1) dp[0] True for ch in s: nxt [False] * (n 1) for j in range(n): if not dp[j]: continue if ch (: nxt[j 1] True elif ch ): if j 0: nxt[j - 1] True else: nxt[j] True nxt[j 1] True if j 0: nxt[j - 1] True dp nxt return dp[0]注意滚动数组里内层循环j我限制在range(n)也就是最大到n-1这样nxt[j1]不会越界。因为状态中未匹配左括号数最多等于已处理字符数不可能到n1。4.4 三种解法复杂度与推荐场景对比整理成一张表方便你面试前快速回忆解法时间复杂度空间复杂度核心思想推荐场景贪心双变量O(n)O(1)用区间覆盖可能性面试首选写起来最快双栈O(n)O(n)用下标保证匹配顺序需要严谨证明时用动态规划O(n^2)O(n) 或 O(n^2)枚举所有可能状态面试官追问拓展思路时用如果限时 10 分钟我会直接写贪心如果让我给同学讲题我一定会先画双栈的模拟过程如果是在预习字符串 DP 专题那就把 DP 的转移方程背下来。三者各有价值不是简单的谁取代谁的关系。5. 复盘提交记录里的每一个红色报错都是经验5.1 高频 bug 清单结合我自己做题和帮同学 debug 的经验整理下面五个经典错误只用一个计数器。很多人的第一反应是像 20 题那样维护count遇到*不知道加减最后只能碰运气。这题必须用两个变量或两个栈才能覆盖“可能性”这个核心。贪心忘了检查hi 0。少了这行右括号过多的情况会被漏判比如())可能会返回 true。贪心忘了把lo归零。少了这句lo会变成负数最终lo 0判断失效比如())(这种串可能返回错误结果。双栈收尾时不比较下标。这是双栈写法里最隐蔽的 bug字符串*(是标准反例。DP 里j从 0 枚举到 n 导致越界。j 1在j n时会越界必须控制内层循环范围或者把数组多开一位。5.2 两个调试技巧打印状态和构造最小反例这题用眼睛干瞪很难看出 bug我的习惯是打印中间状态。贪心解法可以在每个字符处理完打印lo和hi对照手算结果看哪一步开始不一致。双栈解法打印两个栈的内容以及每次弹出的下标能很直观地看出匹配顺序对不对。另一个技巧是构造最小反例。凡是遇到括号类题目我都建议准备几个“杀手用例”*(测顺序性()*测右括号是否匹配多余左括号)(测最基本的合法边界((*)测左括号过剩(*))测星号充当左括号的情况。把这些用例在纸上走一遍再跑代码基本能覆盖 80% 的隐藏 bug。5.3 从一个题到一条线678 在括号题族里的位置这道题的威力不止于题目本身。你如果正在刷 LeetCode 热门 100 题会发现括号题是成串出现的20 题是基础栈匹配22 题是括号生成32 题是最长有效括号394 题是字符串解码224 题是基本计算器。678 题正好卡在“栈”和“贪心”的交界处把这一题搞透再回头刷 20 和 32 会有俯视的感觉。顺带说一句如果你在做题单时把 994 腐烂的橘子、073 爱吃香蕉的狒狒这类 BFS 和二分题也放进同一阶段练习你会发现它们虽然题型不同但本质上都是在“状态空间”里寻找可行路径。678 的区间贪心是状态压缩腐烂橘子的 BFS 是状态扩散爱吃香蕉的狒狒是答案二分。把这几条线串起来你对算法题的认知会从“刷了多少道”升级成“建立了多少张模型”。我个人刷这题最深的一个体会是括号匹配的平衡量在带通配符的时候真的可以是一个区间而不是一个点。这个思维不只在算法题里有用日常处理各种“存在不确定因素的任务排期”时也非常形象。如果你现在正卡在 678 这道题上别灰心先敲一遍贪心再模拟一遍双栈最后翻翻 DP 的转移表三遍之后你会回来感谢这道题。
