题目描述
思路解析
一句话答案：LeetCode 678 有效的括号字符串：星号可当左、右括号或空串，不枚举每种选法，只跟踪未匹配左括号数的下界 low 与上界 high，扫完 low 归 0 即有效，时间 O(n)、空间 O(1)。
这串括号能不能配成有效的
输入是一串只含左括号、右括号和星号的字符。星号是百变字符，每个都能当成一个左括号、一个右括号，或当成空串什么都不填。问题是：能不能给所有星号各挑一个身份，让整串括号配得刚好——每个左括号都有右括号接上，且任何前缀里右括号都不多于左括号。配得出返回 true，否则 false。
暴力枚举每个星号会炸成什么样
星号的麻烦在于身份要扫到后面才定。一个办法是把每个星号的三种身份全枚举：k 个星号就有 3 的 k 次方种组合，每种都要完整扫一遍验证前缀合法。星号一多就指数级膨胀，几十个就跑不动，得把这堆组合合并成一次扫描。
为什么跟踪一段区间就不漏任何组合
跳出逐个枚举，改盯一个量：扫到当前位置为止，未匹配的左括号还剩几个。不同星号选法让这个数不一样，但把所有选法的取值收在一起，它们始终是一段连续区间 low 到 high。low 是最悲观的下界（星号尽量当右或空），high 是最乐观的上界（星号尽量当左）。
连续性能逐字符验：开局区间只有 0 一个值。每读一字符，遇左括号整段 +1、遇右括号整段 -1 都是平移；遇星号把区间左右各撑一格，下界 -1、上界 +1，仍连续且把原取值都包住。既然每步都保住连续，中间任何整数都对应某种真实选法，只用 low、high 两端点就代表全部、一个不漏。
扫一遍的三条更新规则和收尾判定
落成扫描：low、high 从 0 起步，逐字符从左读。读到左括号，未匹配左括号多一个，low、high 各 +1；读到右括号消耗一个，各 -1；读到星号可左可右可空，撑开区间，low 减 1、high 加 1。每读完一个做两道检查：一旦 high ＜ 0，连最乐观的上界都救不了多出的右括号，返回 false；若 low ＜ 0 就夹回 0，因未匹配左括号数最少是 0，不夹会让后面下界失真。扫完返回 low == 0：下界能摸到 0，就有一种选法让左右配平。
三个题面串的 low、high 各怎么变
先看 「()」：low、high 从 0、0 起步。左括号各 +1 到 1、1；右括号各 -1 回 0、0，全程没到负。扫完 low == 0，返回 true。
再看 「(*)」：起点 0、0。左括号后 1、1；星号撑开成 0、2；右括号 -1 得 -1、1，low 夹回 0 成 0、1。末尾 low == 0，返回 true。
最后 「(*))」：从 0、0 起。左括号后 1、1；星号撑开 0、2；右括号 -1 得 -1、1，low 夹回 0 成 0、1；再一个右括号 -1 得 -1、0，夹回 0、0。high 全程没负，收尾 low == 0，返回 true。
区间法最容易崩的三处
枚举每个星号的三种选法是最大的坑，串一长 3 的 k 次方级组合直接超时，区间法压成两个整数扫一遍才行。第二个坑是忘把 low 夹回非负——负的 low 会带偏后面每步下界，让本该有效的串误判成 false。第三是收尾只看 high、忘判 low：high 只是上界，能否配平取决于下界 low 摸不摸得到 0，末尾必须判 low == 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
关键直觉：所有 * 的选法下，「未匹配左括号数」始终是一段连续区间。我们不关心具体每个 * 选了啥，只盯这段区间的上下界。high 是乐观上界（* 尽量当左），low 是悲观下界（* 尽量当右）。high 掉到负说明右括号怎么都多了；结尾 low 能归 0 说明存在一种选法刚好配平。
例 1（有效） 开始。蓝色光标 cur 停在第 0 个字符。我们维护一段区间 [low, high] = 「当前未匹配 ( 的可能个数」，开局是 [0,0]。下面一个字符一个字符地更新这段区间，并随时检查 high 有没有掉到负。
光标到第 0 个字符，是左括号 (。左括号必然多出一个未匹配的 (，区间整段右移：low、high 各 +1。 更新前 [low,high]=[0,0]，更新后先得到 [1,1]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=1 本就 ≥0，不用夹。 high=1≥0 没触发 false，区间安全落在 [1, 1]，往下一个字符走。
光标到第 1 个字符，是星号 *。星号身份不定——当 ) 时 -1，当空时不变，当 ( 时 +1，所以区间被撑大：low-1、high+1。 更新前 [low,high]=[1,1]，更新后先得到 [0,2]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=0 本就 ≥0，不用夹。 high=2≥0 没触发 false，区间安全落在 [0, 2]，往下一个字符走。
光标到第 2 个字符，是左括号 (。左括号必然多出一个未匹配的 (，区间整段右移：low、high 各 +1。 更新前 [low,high]=[0,2]，更新后先得到 [1,3]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=1 本就 ≥0，不用夹。 high=3≥0 没触发 false，区间安全落在 [1, 3]，往下一个字符走。
光标到第 3 个字符，是右括号 )。右括号必然消耗一个 (，区间整段左移：low、high 各 -1。 更新前 [low,high]=[1,3]，更新后先得到 [0,2]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=0 本就 ≥0，不用夹。 high=2≥0 没触发 false，区间安全落在 [0, 2]，往下一个字符走。
光标到第 4 个字符，是左括号 (。左括号必然多出一个未匹配的 (，区间整段右移：low、high 各 +1。 更新前 [low,high]=[0,2]，更新后先得到 [1,3]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=1 本就 ≥0，不用夹。 high=3≥0 没触发 false，区间安全落在 [1, 3]，往下一个字符走。
光标到第 5 个字符，是星号 *。星号身份不定——当 ) 时 -1，当空时不变，当 ( 时 +1，所以区间被撑大：low-1、high+1。 更新前 [low,high]=[1,3]，更新后先得到 [0,4]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=0 本就 ≥0，不用夹。 high=4≥0 没触发 false，区间安全落在 [0, 4]，往下一个字符走。
光标到第 6 个字符，是右括号 )。右括号必然消耗一个 (，区间整段左移：low、high 各 -1。 更新前 [low,high]=[0,4]，更新后先得到 [-1,3]。
高亮的格子并入已处理区（绿底）。检查铁律②：low 算出来是 -1，但未匹配左括号数不可能为负，夹回 0。 high=3≥0 没触发 false，区间安全落在 [0, 3]，往下一个字符走。
光标到第 7 个字符，是右括号 )。右括号必然消耗一个 (，区间整段左移：low、high 各 -1。 更新前 [low,high]=[0,3]，更新后先得到 [-1,2]。
高亮的格子并入已处理区（绿底）。检查铁律②：low 算出来是 -1，但未匹配左括号数不可能为负，夹回 0。 high=2≥0 没触发 false，区间安全落在 [0, 2]，往下一个字符走。
光标到第 8 个字符，是左括号 (。左括号必然多出一个未匹配的 (，区间整段右移：low、high 各 +1。 更新前 [low,high]=[0,2]，更新后先得到 [1,3]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=1 本就 ≥0，不用夹。 high=3≥0 没触发 false，区间安全落在 [1, 3]，往下一个字符走。
光标到第 9 个字符，是星号 *。星号身份不定——当 ) 时 -1，当空时不变，当 ( 时 +1，所以区间被撑大：low-1、high+1。 更新前 [low,high]=[1,3]，更新后先得到 [0,4]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=0 本就 ≥0，不用夹。 high=4≥0 没触发 false，区间安全落在 [0, 4]，往下一个字符走。
光标到第 10 个字符，是右括号 )。右括号必然消耗一个 (，区间整段左移：low、high 各 -1。 更新前 [low,high]=[0,4]，更新后先得到 [-1,3]。
这个字符处理完，区间落定在 [0, 3]。注意 low 原本算出 -1，但「未匹配左括号数」最少就是 0、不存在负的，所以夹回 0。 这是最后一个字符了，接下来看结尾的 low 能不能归 0。
例 1（有效） 卡死在第 10 个字符（红色）：那一步 high 掉到负，乐观上界都救不了多出来的右括号，无论 * 怎么选都配不平，答案 false。
例 2（无效） 开始。蓝色光标 cur 停在第 0 个字符。我们维护一段区间 [low, high] = 「当前未匹配 ( 的可能个数」，开局是 [0,0]。下面一个字符一个字符地更新这段区间，并随时检查 high 有没有掉到负。
光标到第 0 个字符，是左括号 (。左括号必然多出一个未匹配的 (，区间整段右移：low、high 各 +1。 更新前 [low,high]=[0,0]，更新后先得到 [1,1]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=1 本就 ≥0，不用夹。 high=1≥0 没触发 false，区间安全落在 [1, 1]，往下一个字符走。
光标到第 1 个字符，是星号 *。星号身份不定——当 ) 时 -1，当空时不变，当 ( 时 +1，所以区间被撑大：low-1、high+1。 更新前 [low,high]=[1,1]，更新后先得到 [0,2]。
高亮的格子并入已处理区（绿底）。检查铁律②：low=0 本就 ≥0，不用夹。 high=2≥0 没触发 false，区间安全落在 [0, 2]，往下一个字符走。
光标到第 2 个字符，是右括号 )。右括号必然消耗一个 (，区间整段左移：low、high 各 -1。 更新前 [low,high]=[0,2]，更新后先得到 [-1,1]。
高亮的格子并入已处理区（绿底）。检查铁律②：low 算出来是 -1，但未匹配左括号数不可能为负，夹回 0。 high=1≥0 没触发 false，区间安全落在 [0, 1]，往下一个字符走。
光标到第 3 个字符，是右括号 )。右括号必然消耗一个 (，区间整段左移：low、high 各 -1。 更新前 [low,high]=[0,1]，更新后先得到 [-1,0]。
高亮的格子并入已处理区（绿底）。检查铁律②：low 算出来是 -1，但未匹配左括号数不可能为负，夹回 0。 high=0≥0 没触发 false，区间安全落在 [0, 0]，往下一个字符走。
光标到第 4 个字符，是左括号 (。左括号必然多出一个未匹配的 (，区间整段右移：low、high 各 +1。 更新前 [low,high]=[0,0]，更新后先得到 [1,1]。
这个字符处理完，区间落定在 [1, 1]。 这是最后一个字符了，接下来看结尾的 low 能不能归 0。
例 2（无效） 卡死在第 4 个字符（红色）：那一步 high 掉到负，乐观上界都救不了多出来的右括号，无论 * 怎么选都配不平，答案 false。
边界先想清：空串和单个 * 都 true；开头就 ) 会让 high 立刻为负直接 false；左括号收不尾时结尾 low≠0 也 false；判定看结尾 low 能否归 0。
两个高频追问：连续性靠逐字符的平移/撑大归纳保证；没有 * 时区间退化成单个计数器，就是最经典的括号匹配。
参考代码
def checkValidString(s): low = high = 0 # 未匹配左括号数的可能区间 [low, high] for ch in s: if ch == "(": low += 1; high += 1 elif ch == ")": low -= 1; high -= 1 else: # ch == "*"，可当 ) / 空 / ( low -= 1; high += 1 if high < 0: # 右括号无救地多了 return False if low < 0: # 未匹配左括号数不能为负 low = 0 return low == 0 # 能归零 → 配得平复杂度
- 时间：O(n)，从左到右扫一遍字符串，每个字符只处理一次
- 空间：O(1)，只用 low、high 两个整数，不开额外结构
易错点
面试追问把动画讲成自己的话
追问为什么所有 * 选法下「未匹配左括号数」一定是一段连续区间，而不是一堆离散值？
追问如果没有 *（只有 ( 和 )）这题退化成什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
根据身高重建队列
LeetCode 406 · 中等 · 沿着 贪心 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题