Valid Parenthesis String

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
Example 3:
Input: "(*))"
Output: True
Note:
The string size will be in the range [1, 100].

判断给出的字符串是否满足以下条件
1.一个左括号必须有一个对应的右括号
2.一个右括号必须有一个对应的左括号
3.左括号必须在其对应的右括号之前
'*'可以作为左括号或者右括号或者空字符串

    public boolean checkValidString(String s) {
        //本来这道题目是十分简单的，只要遇到( +1，遇到)则 -1,并且每次操作都判断操作数是否大于0即可
        //但是因为会含有*号，所以处理方式上会麻烦很多，效率也差，所以下面只给出leetcode推荐算法
        /**
         * leetcode推荐算法
         * When checking whether the string is valid, we only cared about the "balance": the number of extra
         * , open left brackets as we parsed through the string
         * 当我们判断一个字符串是否合法时，我们只关心他是否"平衡"：即是我们解析字符串得到的额外的左括号的数量
         * For example, when checking whether '(()())' is valid, we had a balance of 1, 2, 1, 2, 1, 0 as we parse through
         * the string: '(' has 1 left bracket, '((' has 2, '(()' has 1, and so on. This means that after parsing the
         * first i symbols, (which may include asterisks,) we only need to keep track of what the balance could be.
         * 比如，'(()())'是合法的，我们逐个解析字符串可以得到1,2,1,2,1,0
         * 当我们解析'('的时候我们有1个额外的左括号
         * '(('则有两个
         * '(()'第二个和第三个左右括号分别抵消，则得到1个左括号，依照这种方法推算下去即可,如果我们计算最后一个字符的结果为0，则表示这个字符串是合法的
         * 这表示我们只需要关注计算结果就可以了
         * For example, if we have string '(***)', then as we parse each symbol
         * , the set of possible values for the balance is [1] for '('; [0, 1, 2] for '(*';
         * [0, 1, 2, 3] for '(**'; [0, 1, 2, 3, 4] for '(***', and [0, 1, 2, 3] for '(***)'.
         * 再举个例子'(***)',每个符号的计算结果如下
         * '(' ,1
         * '(*',因为*可以是任何字符，所以结果可以是 0,1,2
         * 同理 '(**' 0, 1, 2, 3
         * '(***' 0, 1, 2, 3, 4
         * '(***)' 0, 1, 2, 3
         * Furthermore, we can prove these states always form a contiguous interval.
         * Thus, we only need to know the left and right bounds of this interval.
         * That is, we would keep those intermediate states
         * described above as [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].
         * 此外,我们可以证明这些可能的结果都可以一种连续的区间表示
         * 因此，我们只需要左右边界就可以表示可能的结果了
         * 对于上面的例子'(***)',我们可以这样表述
         * [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].
         */
        /**
         * lo,hi分别表示最少/最多的左括号数量
         */
        int lo = 0,hi = 0;
        for(Character c : s.toCharArray()){
            //当我们解析当前字符串=='('时,lo+1,hi+1
            //当我们解析当前字符串==')'时,左括号被抵消那么 lo-1,hi-1
            //当我们解析当前字符串=='*'时,lo表示左括号最少数量所以我们把*当作)处理，lo-1
            //hi表示左括号最多数量，则我们把*当作(处理，hi+1
            lo += c == '(' ? 1 : -1;
            hi += c != ')' ? 1 : -1;
            //如果hi<0，比如第一个字符就是')'的情况，那么这个字符明显不合法，所以不需要判断直接break
            if(hi < 0){
                break;
            }
            //我们允许lo<0的情况，因为lo小于0是*号造成的，比如(********)这种
            lo = Math.max(0, lo);
        }
        //结果由上面的推论可知，只要==0，那么则是合法的
        return lo == 0;
    }

其实上面算法看起来很玄乎，无外乎就是设定一个最少左括号数，这个数字可以<0,因为你把所有的星号都当成了),但是别忘了星号也可以当成空字符所以用lo = Math.max(0, lo)把星号造成的影响抹去。而最多左括号数在任意时候一定都不能小于0，因为把所有星号都换成(依然抵消不了),再根据规则3可以推断这个字符串一定是不合法的