Problem

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

Solution

class Solution {    public boolean checkValidString(String s) {        return helper(s, 0, 0);    }    private boolean helper(String s, int index, int count) {        if (index == s.length()) {            return count == 0;        }                if (count < 0) return false;        char ch = s.charAt(index);        if (ch == '(') return helper(s, index+1, count+1);        else if (ch == ')') return helper(s, index+1, count-1);        else return helper(s, index+1, count-1) || helper(s, index+1, count+1) || helper(s, index+1, count);    }}