第一次在题单里看到 leetcode678 这五个字符时我以为是又一个简单的括号判断题。LeetCode 678也就是“有效的括号字符串”Valid Parenthesis String在 LeetCode 题解区常年被标记为中等难度却让一批批刷题的人中途破防它的普通版本 LeetCode 20 只需要一个栈可这题多了个*通配符*既可以是左括号也可以是右括号还可以当作什么都没发生。题目其实很短给你一个字符串s里面只有(、)和*问是否存在一种把*解释成(、)或空串的方式让整个字符串变成合法括号串。如果你是从 LeetCode 热门 100 题或者哪个刷题指南点进来的那大概率是想把这题放进“栈与字符串”的技能包里。它适合三类人一是刚刷完 LeetCode 20、22、32 这些括号系列想再上一档的二是面试复习时想把“贪心 区间”这类套路补上的三是在周赛里经常栽在中等题想提高对“状态范围”敏感度的。后面我会按我自己 debug 的顺序来讲先说为什么普通栈思路会绕进去再讲 O(n) 贪心的本质然后给出可复现代码和一批让人一眼上头的反例。1. 一眼看懂题目这不是普通的括号匹配1.1 题目到底在问你什么先过一遍规则。一个合法括号串在从左到右扫描时必须满足两个条件任意前缀里右括号数量不能超过左括号数量也就是“余额”不能变成负数扫描结束后左右括号数量相等余额回到 0。这里把左括号记作 1右括号记作 -1整个合法性就等价于“全程余额非负结尾余额为 0”。LeetCode 678 在这个基础上引入了一个*。*有三张脸可以变成左括号、右括号也可以是一个空字符串也就是对余额不动。注意这里的“空”不是任意通配符很多初学者把它理解成“匹配任意字符”一下子就去想正则表达式了思路直接跑偏。题目限制也不算大原题字符串长度1 s.length 100。这个数据量下哪怕写个 O(n²) 的记忆化搜索也能跑过但面试官极少满足于“能过”他们真正想问的是你能不能在线性时间里、用常数空间判断出来所以接下来我们的目标很明确最优解是 O(n) 时间和 O(1) 空间。1.2 为什么“栈 回溯”容易把人绕晕先看没有*的情况那就是 LeetCode 20 的套路遇到左括号入栈遇到右括号就看栈顶匹配则弹出不匹配直接返回 false。整个过程是确定性的因为每一个字符的语义是唯一的。一旦混入*事情变麻烦了。一个*有三种解释遍历到它的时候你不能简单地压栈因为三种解释都会产生不同的后续状态。有些同学第一反应是深度优先搜索每个*枚举三种情况检查所有分支里有没有一条路能走到结尾且余额为 0。这思路本身没错但复杂度是指数级的字符串稍微长一点就爆了。就算把(index, balance)作为状态做记忆化理论上能压到 O(n²)也已经偏离了这道题最漂亮的地方。我一开始也是这样绕进去的。花半小时写了个带 memo 的递归测试用例全过还觉得挺稳。后来被朋友问了一句“你能不能只用两个变量做”我才意识到这题的真正考点不是搜索剪枝而是你能不能看穿“不确定状态”背后的连续性。这个认知转变比背下这道题的答案重要得多。2. 核心思路拆解把“不确定”看成一段连续区间2.1 区间思维lo 和 hi 分别代表什么关键转变是不要再去想“某一种具体解释下余额是多少”而要想“所有可能的解释下余额会落在哪个范围内”。定义两个变量lo当前所有可能解释中未匹配左括号数量的最小值。hi当前所有可能解释中未匹配左括号数量的最大值。初始状态下空串的余额是 0所以lo hi 0。每读一个字符更新规则可以总结成一张表当前字符lo 的变化hi 的变化直观理解(11余额整体向上平移左括号必然增加)-1-1余额整体向下平移右括号必然消耗左括号*-11最小值来自把*当右括号最大值来自把*当左括号第 3 行是核心也是最容易写错的地方。遇到*时我们要同时考虑三种解释变成(会让余额最大区间上界变大变成)会让最小区间下界变小变成空则维持原状。三种情况合在一起区间就从[lo, hi]扩展成了[lo - 1, hi 1]。你可以把lo和hi想象成一个库存范围你有一批货物其中有些单据写得不清楚可能代表进货也可能代表退货还可能根本不算数。你不需要知道每一张单据最后怎么处理只需要知道仓库里货物数量最多可能到多少、最少可能到多少。只要这个范围里包含 0就存在一种让仓库恰好归零的方案。2.2 区间状态为什么是连续的以及只记两个端点的依据有人会问为什么区间中间的值一定都能取到换句话说如果lo到hi之间某个余额没有对应的*解释怎么办答案是不会出现空洞。每处理一个*原来的区间[lo, hi]会扩展成三个新区间的并集也就是[lo - 1, hi 1]处理普通左右括号则只是整体平移不会破坏区间连续性。因为每一步都只是平移或扩展一个连续区间所以区间始终保持连续。这也正是“两个端点就能刻画全部状态”的前提只要端点对中间值自然都在。这个过程可以用一个数学归纳来理解。前缀长度为 0 时合法余额的集合是{0}显然是连续区间。假设处理完某个前缀后所有合法解释对应的余额恰好填满[lo, hi]此时再加入一个新字符如果是(所有余额加 1区间变成[lo 1, hi 1]。如果是)所有余额减 1区间变成[lo - 1, hi - 1]其中低于 0 的部分非法需要剔除。如果是*每个余额选择加 1、减 1 或不变相当于把三个相邻区间并起来得到[lo - 1, hi 1]。所以从“合法状态集合”的层面看这道题根本不是搜索问题而是一个区间收缩扩张问题。我第一次看别人题解时被“贪心”两个字吓住了其实背后就是这套区间思维。2.3 最后的判定为什么是 lo 0还有一个很容易被忽略的细节每次更新完lo和hi之后要做两件事。第一件事检查hi 0。如果hi都小于 0说明即使在最乐观、把所有*都想象成左括号的情况下当前右括号的数量也压过了左括号区间里所有状态都已经掉进负数区域。这种情况下不管后续字符是什么都不可能再拯救回来直接返回 false。第二件事把lo截到 0。为什么可以随便截因为lo小于 0 时比如 -2其含义是“最少解释下出现了 2 个多余右括号”。但我们可以把刚才某些被当成右括号的*改成空字符串让这部分多出来的右括号消失。换句话说最小值小于 0 不意味着无解只要最大值还非负区间里就还有一条路能保持余额非负。所以安全做法是lo max(lo, 0)。到整个字符串扫描结束区间已经变成[lo, hi]其中lo被截过hi在过程中始终没小于 0。如果lo 0说明区间里包含 0也就是说存在一种*的赋值让最终余额归零。反过来说如果lo 0说明即使把所有*都尽量变成右括号仍然剩着左括号没配平当然非法。很多半途而废的题解只写“维护 lo 和 hi”不讲为什么结尾只用看 lo于是读者遇到hi很大、lo 0的情况就开始慌。其实只要理解了区间含义结尾条件自然就记牢了。3. 实操过程与核心环节实现3.1 O(n) 时间、O(1) 空间的贪心解法Python Java先把最推荐的写法给出来。这是我在 LeetCode 678 题解区里见到的最高频实现也是我每次面试都会优先选择的一版。class Solution: def checkValidString(self, s: str) - bool: lo 0 # 未匹配左括号数量的最小可能值 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; } }两个版本的核心逻辑完全一致。这里有一个命名上的小建议把变量命名为lo和hi不如命名为minBalance和maxBalance来得直观。因为在实际代码 review 时你写hi 0的判断面试官不一定立刻反应出“最大余额都成负数了说明彻底没救”但如果变量名直接叫maxBalance这句话就非常好讲。我见过有人把lo命名为left、把hi命名为right结果自己在解释时都分不清哪个是下限哪个是上限越讲越乱。写代码前先把名字想清楚能省很多口舌。3.2 单测推演“(*))” 是怎么走完全程的直接看代码可能还是不够直观我手动模拟一个经典案例(*))。这个字符串在 LeetCode 官方例子里出现过答案是 true因为可以把*当成左括号得到(()))的另一种安排不对仔细看(*))如果把*当成左括号字符串变成(())也就是第 1 个左括号、第 2 个字符*变左括号、两个右括号依次匹配完全合法。用我们的区间变量走一遍扫描位置当前字符lohi说明初始-00空区间0(11余额区间整体上移1*02区间扩散2)-11先减再截断 lo得到 03)-10再减再截断 lo得到 0扫描结束后lo 0所以返回 true。注意位置 2 和位置 3 的lo都先变成了 -1但都被截断了这不是 bug而是“有些*不需要被强行解释成右括号”的体现。再看一个 false 例子)(。扫描第一个字符)时lo -1、hi -1此时hi 0直接返回 false。理由很直接第一个字符就是右括号任何*都帮不了它因为根本没出现过左括号。3.3 双栈解法面试时讲清楚匹配关系的备用方案区间贪心是这道题的最优解但不是唯一解。如果你在面试中第一次见这题没想出来区间思维用一个双栈方案也能解决而且它更符合“匹配”直觉。思路是这样的用两个栈分别存左括号和星号在字符串中的下标。遇到右括号时优先跟左括号栈匹配左括号栈空了再拿星号来顶替左括号如果两个栈都空右括号就落单了直接返回 false。扫描结束后左括号栈里可能还剩下一些(需要用星号栈里位置更靠后的*来匹配。为什么要求位置更靠后因为左括号必须在右括号之前如果*要扮演右括号它的下标必须大于左括号的下标。class Solution: def checkValidString(self, s: str) - bool: opens [] stars [] for i, ch in enumerate(s): if ch (: opens.append(i) elif ch *: stars.append(i) else: # ) if opens: opens.pop() elif stars: stars.pop() else: return False while opens: if not stars: return False star_pos stars.pop() open_pos opens.pop() if star_pos open_pos: return False return True这个双栈写法的优势是每一步都有具体下标做依据逻辑不容易错缺点是额外用了 O(n) 空间。面试时如果被追问“能不能把空间降到 O(1)”再顺势引出区间贪心实际上是很好的展示方式说明你掌握了两种层级的解法。3.4 对称心法从右往左验证一遍区间贪心还有一个非常漂亮的对称版本把字符串反过来用右括号视角扫描。你可以把括号序列从右往左看右括号变成“收益”左括号变成“消耗”星号依旧是可加可减可空。class Solution: def checkValidString(self, s: str) - bool: lo 0 # 从右往左看右括号数量的最小可能值 hi 0 for ch in reversed(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 0这个版本和从左往右的版本理论上完全等价。我建议你在本地跑一组随机用例用两个版本互相验证。如果某一组数据两个版本结果不一致那肯定是你某个边角情况没想透比如漏了对hi 0的检查或者lo截断时机不对。这种“正反双写”的做法不仅仅是为了确认代码正确更是一种锻炼它强迫你从两个方向理解同一个区间模型。面试中如果时间充裕主动提出“这个模型可以双向验证”往往能留下很好的印象。4. 常见问题与排查技巧实录4.1 让我踩过坑的测试用例刷题最怕的不是大用例而是那些用肉眼能推演、却让人想当然的短用例。我整理了几个比较有代表性的你可以拿自己的实现跑一下输入预期观察点*true*可以当空串题目中的基础情况*(false剩下的(无法靠前头的*匹配(*)truea 号段*当空或当左括号都能凑(*))true官方示例区间中途会到 -1 后又截断((*false剩一个左括号*只能救回一部分((*)true*充当右括号和第三个(配对)*(false开头就失败区间直接判死(()*true*在末尾补一个右括号后完全平衡第一次跑通后建议把(*))和((*这两个用例抄到自己的测试函数里。前者验证“lo负值要靠截断来消化”后者验证“结尾必须严格看lo而不是hi”。这两点往往是实现出错的高发区。4.2 写代码时四个不容易察觉的错误第一个错误把lo 0当成立刻失败的信号。这是最经典的低级错误。在扫描(*))的过程中lo会在第 2、3 步变成 -1但整个字符串其实是合法的。正确的做法是把lo截回 0因为最小余额代表“最悲观解释”悲观解释失败不代表其他解释失败。只有hi 0才是所有解释都失败。第二个错误返回条件写成了return hi 0甚至return hi 0。到了末尾hi可能比 0 大很多这个时候不能说明合法因为最大值大意味着*全部被解释成了左括号可能剩了一堆左括号没匹配。正确检查对象一定是最小值lo它代表了“能不能通过调整*的解释硬凑出余额 0”。第三个错误*的更新写反。有人写*时顺手lo 1; hi - 1觉得星号又是加又是减其实方向错了。结合区间思维lo要挖掘“最少剩余左括号”所以应当把星号当成右括号来压低hi要挖掘“最多剩余左括号”所以应当把星号当成左括号来抬高。如果记反了很多真用例都会误判。第四个错误双栈解法里最后一步只判断stars非空忘了比较下标。比如*(这个例子双栈扫描后stars [0]、opens [1]如果只判断stars非空就返回 true那就错了星号在左括号前面不能反过来充当右括号。只有star_pos open_pos才匹配得上。4.3 和 LeetCode 相邻题目的连点从热门 100 题到周赛LeetCode 678 不是孤立的题。把它放进“括号家族”里你会看到一条清晰的难度递进线。LeetCode 20 有效括号确定性匹配标准栈。LeetCode 22 括号生成回溯 剪枝。LeetCode 32 最长有效括号动态规划或栈求长度而不是判断合法性。LeetCode 921 使括号有效的最少添加单纯贪心计数不需要区间。LeetCode 678判断合法性但引入不确定状态需要区间贪心。如果你已经刷过这些题再来做 678会明显感受到一种“旧知识 新变量”的组合括号合法性的判断方法你早就掌握了难点在于能否把*的三种选择压缩成两个极值。顺便说一句网上经常把 LeetCode 994 腐烂的橘子、LeetCode 073 爱吃香蕉的狒狒这些题放在一起讨论它们其实代表了完全不同的解题范式994 是 BFS 分层扩散073 是二分答案边界搜索678 是单遍扫描的区间维护。这些题虽然标签不同但共同点是“状态不是单一数字而是需要维护一个范围或集合”。如果你在准备 LeetCode 周赛 430多刷几道这种“范围状态”的题能够明显提高对周赛中等题的直觉判断力。5. 实战复盘与扩展思路5.1 三分钟思维路径从题意到贪心如果面试中遇到这道题我会在脑中快速过这三步而不是直接背代码。第一步把括号合法性翻译成“扫描过程余额非负结尾余额为零”。这是所有括号题的公共底座先把这层地基打牢。第二步观察*的三重身份意识到余额不再是一个点而是一段区间。这不是“优化技巧”而是题目的天然结构每一个*都会让区间向外扩展一次。第三步根据区间模型写出更新规则并处理两类边界hi掉到负数直接失败lo掉到负数要截断。最后检查lo 0。这套流程的核心价值在于它不会因为你忘了某个样例而崩掉。你不需要记住(*))这个特例只要理解了区间任何用例都是同一个模型的不同输入而已。5.2 如果把“能否合法”改成“有多少种合法方式”很多人刷完 678 后会想既然判断合法这么简单那统计到底有多少种不同的*替换方式能合法是不是也能贪心答案是不能。区间贪心只是确认“存在性”它把所有解释合并成了一个范围但丢掉了每种解释的具体计数信息。如果要求统计方案数最直接的做法是动态规划设dp[i][j]表示前i个字符处理后余额为j的方案数。j的范围是0到字符串长度所以复杂度是 O(n²)。遇到*时做三方向转移分别对应*变成左括号、右括号和空串。这类扩展题我推荐你顺手做一遍不是为了应付面试而是为了对照理解为什么“存在性判断”可以只维护两个极值“计数”却必须维护整个分布。这个区别在动态规划里非常常见提前体会一次后面遇到类似的“存在 vs 计数”问题就不会再迷路。另外还有一种变形如果把*的限制改掉比如规定*不能当作空串那区间的转移规则就需要微调但整体框架不变。这说明一个算法的骨架只要扎实加约束、改条件都只是外层参数的变化。我在实际面试中被问到 LeetCode 678 时通常会先快速说一句“这题可以同时用双栈和区间贪心做双栈更直观贪心更省空间”然后再根据面试官的兴趣决定展开哪个。如果你只背其中一个解法遇到追问“有没有更优空间复杂度”就会卡壳两个解法都理解反而能从对比中展示出对问题的全局把握。最后再分享一个小技巧写这题代码时强烈建议把变量名写成lo和hi并在注释里注明“最小剩余左括号”和“最大剩余左括号”。我第一次在模拟面试中讲这题就是因为变量名起得太抽象讲到lo max(lo, 0)时把自己绕进去了面试官也跟着皱眉头。后来养成“先定义范围端点、再写转移”的习惯不管是在 LeetCode 678 上还是之后刷到其它区间类题目都很少再出现“代码能过但讲不清”的尴尬。