678. Valid Parenthesis String

https://leetcode.com/problems/valid-parenthesis-string/

由()和*构成的字符串，*可替换成(或)，问最后是否匹配。单类型括号匹配题和301等一样，遍历+1-1。上界max_op遇到不是)的字符+1，否则-1，统计最多有多少没有匹配的(，当max_op< 0时说明(和*加起来也不能和)抵消，Invalid；下界min_op遇到(+1，否则-1，统计至少有多少(没有被匹配【最小值为0】，也就是需要强制匹配的(数量，当min_op最后大于0，说明(要比*和)加起来还多。当遍历完上下界都合法，说明一定能有一种方法给*赋值使得+1-1最后的结果为0。

/*
 * @lc app=leetcode id=678 lang=cpp
 *
 * [678] Valid Parenthesis String
 */

// @lc code=start
class Solution {
public:
    bool checkValidString(string s) {
        int min_op = 0, max_op = 0;
        for (const auto c : s) {
            if (c == '(') ++min_op;
            else --min_op;
            if (c != ')') ++max_op;
            else --max_op;
            if (max_op < 0) return false;
            min_op = max(0, min_op);
        }
        return min_op == 0;
    }
};
// @lc code=end

还有更加像301的正反两遍遍历的解法。正着把*都看作(做统计+1-1，看是否出现负数；反着把*看作)且)+1(-1，同样看是否出现负数。如果都不出现负数，说明一定可以让其中一部分*变为(，另一部分变为)使得最终match。会不会存在同一个*从左边遍历要求变成(才合法，从右边遍历要求变成)才合法的情况？并不会，因为从左边遍历要变成(说明*右侧)比*左侧未匹配的(多，同理后面的条件说明*右侧)比*左侧未匹配(少，冲突。

class Solution:
    def checkValidString(self, s: str) -> bool:
        res, sc = 0, 0
        for c in s:
            if c == ')':
                res -= 1
                if res + sc < 0:
                    return False
            elif c == '(':
                res += 1
            else:
                sc += 1
        res, sc = 0, 0
        for c in reversed(s):
            if c == ')':
                res += 1
            elif c == '(':
                res -= 1
                if res + sc < 0:
                    return False
            else:
                sc += 1
        return True