# 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)