678 Valid Parenthesis String

678. Valid Parenthesis String

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种可能性，即"*"表示为左括号，"*"表示为右括号，"*"为空。

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的个数即可。

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)