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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/exhaustive-search/remove-invalid-parentheses/678.-valid-parenthesis-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.