LeetCode 678. 有效的括号字符串
题目描述
题意分析
字符串只包含左括号、右括号和星号。每个星号都可以独立解释为一个左括号、一个右括号，或者不产生字符；判断是否存在一种解释，使整个字符串成为有效括号串。
有效不仅要求最终左右括号数量相等，还要求任意前缀里右括号都不能多于左括号，即右括号必须匹配它之前的左括号。只需找到一种可行解释，不要求所有星号取同一种含义，也不要求所有解释都有效。
解法：贪心维护未匹配左括号范围
核心思路
[!blue]
从左到右处理时，一个解释是否还能继续，只取决于它留下多少个尚未匹配的左括号。没有星号时这个数量是一个确定值；有星号时可能有多个值。用
low、high表示当前前缀所有合法解释中，这个数量的最小值和最大值。这些可行值始终构成连续的整数区间。空前缀只有数量
0；遇到左括号时，每个可行值都加一，遇到右括号时都减一；遇到星号时，每个可行值可以减一、不变或加一，原区间的三种平移合在一起仍没有空缺。因此保存两个端点，就足以保留所有可能性，不需要枚举每个星号的具体选择。对左括号，执行
low++、high++；对右括号，执行low--、high--；对星号，下界尝试把它当右括号，上界尝试把它当左括号，执行low--、high++，中间值已经包含把它当空串的可能。转移后，负数表示某个前缀已经有右括号找不到前面的左括号。若连最大的
high都小于零，所有解释都失败，应立即返回false，后面的字符无法补救先前的顺序错误。若只是low小于零，仍可能存在合法解释，只需丢掉区间中的负数，将low截到0。扫描结束时，所有保留状态都满足前缀约束。只要区间包含
0，就存在一种解释没有剩余左括号，整个字符串有效；因为下界已经非负，这等价于low == 0。high仍大于零只说明还存在其他未配平的解释，不影响存在性结论。
解题步骤
- 令
low = high = 0，表示空前缀只可能剩余零个左括号。- 依次读取字符：左括号让两端都加一，右括号让两端都减一，星号让下界减一、上界加一。
- 若
high < 0，说明当前前缀无任何合法解释，立即返回false。- 否则将
low截断到至少0，保留本轮仍合法的计数范围。- 全部字符处理完后，返回
low == 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)$，
n为字符串长度，每个字符只引起常数次端点更新。- 空间复杂度：$O(1)$，用两个端点表示全部可行计数。
关键点总结
[!green]
- 维护的是合法解释集合的范围，两个端点不必来自同一种星号选择。
- 可行计数连续，才能用最小值和最大值完整表示，而不是近似猜测。
- 上界为负表示全部失败，下界为负只需去掉不合法的一部分。
- 每轮验证前缀，最后验证能否归零，两个条件缺一不可。
易错点总结
[!yellow]
low < 0就返回失败，会误删仍可通过空串或左括号解释保留的合法方案。- 最后要求
high == 0，把“存在一种合法解释”误写成了“所有解释都配平”。- 只在循环结束检查上界，后面的左括号可能掩盖前面已经失败的前缀。
- 把星号固定成一种符号，会丢失其他取值才能成立的方案。
- 只统计三类字符总数，不检查前缀，会忽略括号必须先开后闭的顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 20. 有效的括号 | 简单 | 无星号时是普通括号匹配，本题星号有三种解释，可用未匹配左括号数量的可能区间压缩分支。 |