LeetCode 678. 有效的括号字符串
目录
题目描述
题意分析
给定只含
(、)、*三种字符的字符串，其中每个*可以独立地被解释成左括号、右括号或空字符串，问是否存在某一组解释，使整个字符串成为合法的括号序列。合法的含义有两条：任意前缀中右括号数量都不超过左括号数量；整串左右括号数量相等。第一条是逐位的约束，第二条是全局的约束，两条都必须满足。
约束里
n不超过 100，量级很小，甚至允许「按位置与未匹配数量两个维度枚举全部可行状态」这种平方级做法通过；但*的数量也可能接近 100，把每个*的三种解释全部枚举出来是指数级，一定超时。题目只问「是否存在」，不要求输出任何一种具体的解释方案，这说明中间过程无需保存分配细节。需要留意的边界情形：空串合法；单个
*合法（当作空串）；以)开头必定不合法；*)合法（*当左括号）；(*也合法（*当右括号）；全为*的串无论长度奇偶都合法。
解法：贪心维护未匹配左括号范围
核心思路
问题关键： 每个
*都有三种解释，逐个枚举需要 $O(3^k)$。判断括号是否合法其实只依赖一个状态：当前前缀还有多少个未匹配的左括号，并且这个数量在任何合法前缀中都不能为负。为什么选择区间贪心： 扫描一个前缀后，可行的未匹配数量构成连续区间。确定的括号会让整个区间平移；
*可以让数量减一、不变或加一，仍不会产生空洞。因此不必保存所有方案，只维护最小值low和最大值high，把 $O(n^2)$ 的状态 DP 压成一次扫描。不变量： 扫描完当前前缀后，
[low, high]恰好表示所有仍满足前缀合法性的解释中，未匹配左括号数的可行范围。转移规则如下：
- 遇到
(：low++、high++；- 遇到
)：low--、high--；- 遇到
*：最少可当右括号，最多可当左括号，所以low--、high++。正确性： 上述转移覆盖了当前字符对区间两端的全部可能。若
high < 0，连未匹配数最多的方案都出现右括号过剩，说明不存在合法解释；若只有low < 0，只是部分方案非法，将下界截为 0 即可。区间连续性保证截断后仍精确表示全部可行数量。扫描结束时low == 0，等价于存在一种解释能把所有左括号恰好匹配完。
解题步骤
- 初始化
low = high = 0，表示空前缀的未匹配数为 0。- 从左到右扫描，根据字符更新上下界。
- 每轮先检查
high < 0，若成立立即返回false。- 再执行
low = max(low, 0)，去掉未匹配数为负的非法方案。- 扫描结束返回
low == 0。口述示例：
"(*))"的区间依次是[1,1]、[0,2]、[0,1]、[0,0]，最终存在配平方案，所以返回true。边界与反例： 以
)开头会立刻令high < 0；全是*时始终可以把它们当空串。不能只检查最终数量，例如")("的左右括号总数相等，但第一个前缀已经非法。
代码实现
class Solution {
public boolean checkValidString(String s) {
int low = 0;
int high = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
low++;
high++;
} else if (ch == ')') {
low--;
high--;
} else {
low--;
high++;
}
if (high < 0) {
return false;
}
low = Math.max(low, 0);
}
return low == 0;
}
}
func checkValidString(s string) bool {
low, high := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
low++
high++
} else if s[i] == ')' {
low--
high--
} else {
low--
high++
}
if high < 0 {
return false
}
if low < 0 {
low = 0
}
}
return low == 0
}
复杂度分析
- 时间复杂度为 $O(n)$，只从左到右扫描一次，每个字符做常数次运算。
- 空间复杂度为 $O(1)$，只维护区间的两个端点。
关键点总结
low表示“最少还可能剩多少左括号”，high表示“最多还能剩多少左括号”。high < 0代表所有方案都失败；low < 0只代表部分方案失败，二者不能同样处理。- 前缀合法性必须在每轮检查，后面的左括号不能补救前面已经多出的右括号。
- 结束时检查
low == 0，因为只需存在一种能配平的解释，并不要求所有解释都配平。
易错点总结
low < 0就返回false：如"*()"，把*当空串即可合法。- 循环结束检查
high == 0：如"(*"，虽然high > 0，仍可把*当右括号。- 把
high < 0的检查放到循环外：后续的(可能掩盖此前已非法的前缀。- 将
*固定解释成一种括号：会丢掉另外两种可行选择。- 只统计三类字符的总数，不维护前缀：无法识别
")("这类顺序错误。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 20. 有效的括号 | 简单 | 字符全部确定但有三种括号类型，必须用栈记录待匹配的具体符号，不存在可行区间 |
| 22. 括号生成 | 中等 | 要输出全部合法方案而非判定可行性，用回溯并靠左右括号剩余量剪枝 |
| 32. 最长有效括号 | 困难 | 求最长合法子串的长度，需要用栈保存下标或按位置做状态转移，不只是判合法 |
| 301. 删除无效的括号 | 困难 | 串中混有字母，要删最少字符并输出所有互不相同的结果，重点在先算删除数量再搜索去重 |
| 856. 括号的分数 | 中等 | 输入保证合法，重点变成沿嵌套层次累积分值，与合法性判断无关 |
| 1249. 移除无效的括号 | 中等 | 只需给出任意一个合法结果，两趟扫描标记待删下标后重建字符串即可 |
| 1614. 括号的最大嵌套深度 | 简单 | 输入已保证合法，只需记录计数器的历史最大值，没有任何不确定字符 |