LeetCode : 678. Valid Parenthesis String

[congr]

https://leetcode.com/problems/valid-parenthesis-string/

[congr]

class Solution {
    public boolean checkValidString(String s) {
        if (s.isEmpty()) return true;

        return check(s.toCharArray(), 0, 0);
    }

    boolean check(char[] ch, int p, int cnt) {
        if (p == ch.length) return cnt == 0;
        if (cnt < 0) return false; // !!! cnt can't be negative. ()) case

        if (ch[p] == '(') return check(ch, p+1, cnt+1);
        else if (ch[p] == ')') return check(ch, p+1, cnt-1);
        else return check(ch, p+1, cnt) ||   // '*' is empty
                    check(ch, p+1, cnt+1) || // '*' is '('
                    check(ch, p+1, cnt-1);   // '*' is ')'
    }
}