> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/exhaustive-search/remove-invalid-parentheses/678.-valid-parenthesis-string.md).

# 678. 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。

```cpp
/*
 * @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。会不会存在同一个\*从左边遍历要求变成(才合法，从右边遍历要求变成)才合法的情况？并不会，因为从左边遍历要变成(说明\*右侧)比\*左侧未匹配的(多，同理后面的条件说明\*右侧)比\*左侧未匹配(少，冲突。

```python
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
```