Java dfs + memorization solution.


  • 0
    int [][] memo;
    public boolean checkValidString(String s) {
        if (s == null || s.length() == 0) return true;
        memo = new int[s.length()][s.length()]; // store visited conditions
        return isValid (s, 0, 0);
    }
    public boolean isValid(String s, int count, int i) { // count is the number of '(' in the "stack". i is current index in s. 
        if (count < 0) return false;
        if (i == s.length()) {
            return count == 0;
        }
        if (memo[count][i] != 0) {
            return memo[count][i] == 1;
        }
        if (s.charAt(i) == '(') {
            if (isValid(s, count + 1, i+1)) memo[count][i] = 1;
            else memo[count][i] = -1;
        }
        else if (s.charAt(i) == ')') {
            if (count == 0) memo[count][i]= -1;
            else {
                if (isValid(s, count - 1, i+1)) memo[count][i] = 1;
                else memo[count][i] = -1;
            }
        }
        else { // s.charAt(i) = '*' 
            // treat '*' as '(', '', ')'.
            boolean res = isValid(s, count+1, i+1) || isValid(s, count, i+1) || isValid(s, count - 1, i+1);
            if (res) memo[count][i] = 1;
            else memo[count][i] = -1;
        }
        return memo[count][i] == 1;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.