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:
Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
An empty string is also valid.
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True

backtracking

之前这题有不带*的情形，当时是用stack做的。那有了星号，我不知道怎么处理星号了。也想到能把三种情况都试一下，但是没想到怎么搞，就算这么做了，如果*太多，分叉的情况就会乘3再成3，复杂度很高吧，就没想下去了。看到别人用这个思路做了，回溯做的，没有超时。
我试着模仿了一下，遇到了很多问题：

1. 写成return dfs(s, count ++, start ++);
这么做IDE会提示你count, start的值没有被用到，我很疑惑。后来想通了，因为++在后面的时候，是执行完了当前语句再自增的，所以进入下一层循环回来之后再增加已经没卵用了。

2. 写成return dfs(s, ++count , ++start);
跟1不同的是，这么做虽然改变了count和start的值，但是这么做无异于先count ++再把count当作参数传入下一层递归，问题是这么做就没有恢复现场的-- 操作了。所以，只能count + 1这么做。递归的参数要慎用自增运算符。

    public boolean checkValidString(String s) {
        if (s == null || s.length() == 0) return true;
        return dfs(s, 0, 0);
    }

    private boolean dfs(String s, int count, int start) {
        if (count < 0)
            return false;
        if (start >= s.length())
            return count == 0;
        if (s.charAt(start) == '(') {
            return dfs(s, count + 1, start + 1);
        }
        if (s.charAt(start) == ')') {
            return dfs(s, count - 1, start +1);
        }
        if (s.charAt(start) == '*') {
                //一旦遇到true就结束递归，一层层返回true
            return dfs(s, count + 1, start + 1)
                    || dfs(s, count - 1, start + 1)
                    || dfs(s, count, start + 1);
        }
        return count == 0;
    }

或写成：

class Solution {
    public boolean checkValidString(String s) {
        return check(s, 0, 0);
    }
    
    private boolean check(String s, int start, int count) {
        if (count < 0) return false;
        
        for (int i = start; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count++;
            }
            else if (c == ')') {
                if (count <= 0) return false;
                count--;
            }
            else if (c == '*') {
                return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count);
            }
        }
        
        return count == 0;
    }
}

One pass

看到一种O(n)的one pass解法，

    public boolean checkValidString(String s) {
        int low = 0;
        int high = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                low++;
                high++;
            } else if (s.charAt(i) == ')') {
                if (low > 0) {
                    low--;
                }
                high--;
            } else {
                if (low > 0) {
                    low--;
                }
                high++;
            }
            if (high < 0) {
                return false;
            }
        }
        return low == 0;
    }

当遇到*的时候，low要--同时high要++；
high is tracking maximum number of open braces possible '('.
if it encounters a *, it considers it as '('
low is tracking minimum number of open braces.
If it encounters a *, it considers it as ')'
In the end, if high is negative, that means there were too many ')'
If low < 0, it means there are more ')' than '(', which is invalid
https://discuss.leetcode.com/topic/103936/short-java-o-n-time-o-1-space-one-pass/6
不太懂，以后有机会再看吧