678. Valid Parenthesis String

678. 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:

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].

------------------------
ref: https://leetcode.com/problems/valid-parenthesis-string/discuss/107577/Short-Java-O(n)-time-O(1)-space-one-pass

遇到'*'可以生成3种可能) = -1, "" = 0, ( = +1。 另一关键在于所有的可能性都是连续的 0, 1, 2,....
保持一个最小最大，如果最后最小能到0，说明可以获得合法的string

class Solution {
    public boolean checkValidString(String s) {
        int low = 0, hi = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                hi++;
                low++;
            }else if (c == ')') {
                if (low > 0) {
                    low--;
                }
                hi--;
            }else if (c == '*') {
                if (low > 0) {
                    low--;
                }
                hi++;
            }
            if (hi < 0) return false;
        }
        
        return low == 0;
    }
}