678 Valid Parenthesis String

N^3 DP, there should have N^2 DP, check out https://leetcode.com/problems/valid-parenthesis-string/solution/

class Solution {
    public boolean checkValidString(String s) {
        if (s == null || s.length() == 0) return true;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++){
            char c = s.charAt(i);

            if (c == '*') dp[i][i] = true;
        }

        for (int size = 1; size <= n; size++){
            for (int i = 0; i + size < n; i++){
                char start = s.charAt(i);
                char end = s.charAt(i + size);
                boolean temp = false;
                if ( (start == '(' || start == '*') && (end == ')' || end == '*') ){
                    // 1. mid is palindrome
                    if (dp[i + 1][i + size - 1]) temp = true;
                    // 2. two halves are palindrome
                    for (int k = i + 1; k < i + size; k++){
                        if (dp[i][k] && dp[k + 1][i + size]) temp = true;
                    }
                    if (size == 1) temp = true;
                }
                dp[i][i + size] = temp;
            }
        }

        return dp[0][n - 1];
    }
}