# 678 Valid Parenthesis String

## 678. [Valid Parenthesis String](https://leetcode.com/problems/valid-parenthesis-string/description/)

## 1. Question

Given a string containing only three types of characters: '(', ')' and '\*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis`'('`must have a corresponding right parenthesis`')'`.
2. Any right parenthesis`')'`must have a corresponding left parenthesis`'('`.
3. Left parenthesis`'('`must go before the corresponding right parenthesis`')'`.
4. `'*'`could be treated as a single right parenthesis`')'`or a single left parenthesis`'('`or an empty string.
5. An empty string is also valid.

**Example 1:**

```
Input: "()"
Output: True
```

**Example 2:**

```
Input: "(*)"
Output: True
```

**Example 3:**

```
Input: "(*))"
Output: True
```

**Note:**

1. The string size will be in the range \[1, 100].

## 2. Implementation

**(1) Recursion**

思路: 如果这题没有"\*"，那么只要维护一个变量count，从左到右扫一遍，count在过程中不为负，且最后count等于0即可。但现在多了一个"\*"，那我们就通过递归尝试3种可能性，即"\*"表示为左括号，"\*"表示为右括号，"\*"为空。

```java
class Solution {
    public boolean checkValidString(String s) {
        return check(s, 0, 0);
    }

    public boolean check(String s, int pos, int count) {
        if (pos == s.length()) {
            return count == 0;
        }

        if (count < 0) {
            return false;
        }

        if (s.charAt(pos) == '(') {
            return check(s, pos + 1, count + 1);
        }
        else if (s.charAt(pos) == ')') {
            return check(s, pos + 1, count - 1);
        }
        // check all possible cases when current character is "*"
        else {
            return check(s, pos + 1, count + 1) || check(s, pos + 1, count - 1) || check(s, pos + 1, count);
        }
    }
}
```

**(2) Two Pointers**

思路: 用两个变量，low表示把"\*"看做右括号时，左括号的个数(即左括号的lower bound), high表示把"\*"看做左括号时，左括号的个数(即左括号的upper bound)。显然，当high小于0时，说明即使把"\*"看做左括号, 也不能够抵消右括号，所以返回false。那么从左到右扫一遍输入string，遇到左括号时，low和high都加1，遇到右括号时，只有low大于0时才减1,这是为了保证low不小于0，high减1。遇到"\*"时，根据high的定义high加1，low大于0才减1。最后查看low的个数即可。

```java
class Solution {
    public boolean checkValidString(String s) {
        int low = 0, high = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                ++low;
                ++high;
            }
            else if (c == ')') {
                if (low > 0) {
                    --low;
                }
                --high;
            }
            else {
                if (low > 0) {
                    --low;
                }
                ++high;
            }

            if (high < 0) {
                return false;
            }
        }
        return low == 0;
    }
}
```

## 3. Time & Space Complexity

**Recursion:** 时间复杂度O(3^n), n是输入字符串长度。最坏的情况是输入string全是"\*", 那么每个"\*"都有3种可能性，空间复杂度O(n)，主要是递归的开销，递归深度最多为n

**Two Pointers:** 时间复杂度O(n), 空间复杂度O(1)


---

# Agent Instructions: 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://protegejj.gitbook.io/algorithm-practice/leetcode/recursion/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.