有效的括号字符串 图解题解

这串括号能不能配成有效的

输入是一串只含左括号、右括号和星号的字符。星号是百变字符，每个都能当成一个左括号、一个右括号，或当成空串什么都不填。问题是：能不能给所有星号各挑一个身份，让整串括号配得刚好——每个左括号都有右括号接上，且任何前缀里右括号都不多于左括号。配得出返回 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。

Python

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          # 能归零 → 配得平

C++

bool checkValidString(string s) {
    int low = 0, high = 0;            // 区间 [low, high]
    for (char ch : s) {
        if (ch == "("[0]) { low++; high++; }
        else if (ch == ")"[0]) { low--; high--; }
        else { low--; high++; }        // "*"
        if (high < 0) return false;    // 右括号多了
        if (low < 0) low = 0;          // 夹回非负
    }
    return low == 0;
}

Java

public boolean checkValidString(String s) {
    int low = 0, high = 0;             // 区间 [low, high]
    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;     // 右括号无救地多了
        if (low < 0) low = 0;           // 夹回非负
    }
    return low == 0;
}