678.Valid Parenthesis String

1

https://leetcode.com/problems/valid-parenthesis-string/discuss/107577/Short-Java-O(n)-time-O(1)-space-one-pass
class Solution {
    public boolean checkValidString(String s) {
        if(s == null || s.length() == 0)
            return true;
        return dfs(s.toCharArray(), 0, 0, 0, s.length());
    }
    public boolean dfs(char[] s, int pos, int leftCnt, int rightCnt, int n){
        if(rightCnt > leftCnt)
            return false;
        if(pos == n){
            if(leftCnt == rightCnt)
                return true;
            else
                return false;
        }
        else{
            char c = s[pos];
            if(c == '('){
                return dfs(s, pos + 1, leftCnt + 1, rightCnt, n);
            }
            else if(c == ')'){
                return dfs(s, pos + 1, leftCnt, rightCnt + 1, n);
            }
            else{
                boolean val1 = false;
                val1 = dfs(s, pos + 1, leftCnt, rightCnt, n);
                boolean val2 = false;
                val2 = dfs(s, pos + 1, leftCnt + 1, rightCnt , n);
                boolean val3 = false;
                if(leftCnt > rightCnt)
                    val3 = dfs(s, pos + 1, leftCnt, rightCnt + 1, n);
                return val1 || val2 || val3;
            }
        }
    }
}