企业官网建设流程全解析

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 最多到 100，3^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。因此lo++，hi++。

遇到')'：这是一个确定的右括号，无论前面怎么解释，它都要消耗一个左括号。所以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 == 0

Java 版本长得几乎一样：

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归零为 0，hi = 1，最终lo == 0，返回 true。
• "("：lo = 1，hi = 1，最终lo == 1，返回 false。
• ")"：lo = -1归零，hi = -1，hi < 0直接返回 false。
• "((*)"：过程不细算，最终lo应该为 1，返回 false。
• "(*)"：最终lo为 0，返回 true。
• "(*))"：最终lo为 0，返回 true。

时间和空间复杂度都很漂亮：一趟扫描，O(n) 时间，O(1) 空间。这也是面试里最推荐给出的方案，因为写起来快，解释清楚后面试官基本都能跟上。

3. 双栈模拟：拒绝玄学，用下标来证明匹配顺序

3.1 为什么栈在这种题里还能用

贪心跳过了顺序这个细节，只靠数字在推。但如果你在面试时想讲得更“扎实”，或者面试官追问“你怎么证明存在性”，双栈解法是更好的回答。

普通的括号匹配问题用栈记录每个'('的位置，遇到')'时弹栈，遇到栈空则说明右括号多余。但这题多了一批可以“救火”的*，它们既能顶替左括号也能顶替右括号。我们需要两个栈：

• leftStack：记录所有'('的下标；
• starStack：记录所有'*'的下标。

遇到')'时，优先用左括号栈来匹配；如果左括号栈空了，才考虑用星号栈来顶替左括号。为什么优先用左括号？因为*是“万能救兵”，它应该留给更麻烦的局面，例如后面没有左括号可用时。这也是贪心策略在栈解法里的体现。

3.2 一个案例走通全过程

拿字符串"(*))"举例，这个用例能覆盖所有分支。

下标从 0 开始。

• i=0，字符'('：入 leftStack，栈内容 [0]。
• i=1，字符'*'：入 starStack，栈内容 [1]。
• i=2，字符')'：leftStack 非空，弹出 0，匹配成功。此时 leftStack = []，starStack = [1]。
• i=3，字符')'：leftStack 空，starStack 非空，弹出 1，让这个星号充当左括号去匹配。匹配成功。
• 遍历结束，leftStack 和 starStack 都为空，返回 true。

再看一个非法串"*("：

• i=0，'*'入 starStack，[0]。
• i=1，'('入 leftStack，[1]。
• 遍历结束，leftStack 非空，需要用 starStack 里的星号去匹配左括号。
• 弹出比较：leftStack 弹出 1，starStack 弹出 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][j+1] = true；
• 如果ch == ')'：只有j > 0时才能消耗一个左括号，所以dp[i][j-1] = true；
• 如果ch == '*'：三种身份都允许，所以空串时dp[i][j] = true，当左括号时dp[i][j+1] = 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[j+1]不会越界。因为状态中未匹配左括号数最多等于已处理字符数，不可能到n+1。

4.4 三种解法复杂度与推荐场景对比

整理成一张表，方便你面试前快速回忆：

如果限时 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 的转移表，三遍之后你会回来感谢这道题。