44. Wildcard Matching

dp[i][j]: the matching p[0:j] can covert to s[0:i]

in normal thinking: * can be any char or empty so

1.
dp[i][j] = dp[0][j-1] ||  dp[1][j-1] || dp[2][j-1] || ... || dp[i][j-1]

2.
dp[i-1][j] = dp[0][j-1] ||  dp[1][j-1] || dp[2][j-1] || ... || dp[i-1][j-1]

2 replace 1 in part => 
dp[i][j] = dp[i-1][j] || dp[i][j-1]

time: O(mn)

space: O(mn)

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        
        s = "#" + s;
        p = "#" + p;
        
        dp[0][0] = true;
        
        // dp[1~m][0] => false
        
        // start from [0][1], [0][0] has been initailized
        // when input is "", how pattern can match "", use *, so if no * do break, in the following is all false
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j) != '*') { 
                break;
            }
            dp[0][j] = true;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)) {
                    dp[i][j] = dp[i-1][j-1];
                    
                } else if (p.charAt(j) == '*') {
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }
            }
        }
        return dp[m][n];
    }
}