44. Wildcard Matching

Link

Solution

這題跟regular expersion一樣

boolean[][] dp = new boolean[s.length()+1][p.length()+1];

intital DP array

dp[0][0] : true

dp[0][j] : 考慮s為空的狀況，p[j-1]要是*才有可能

簡化問題

1. dp[i][j] = dp[i-1][j-1] iff s[i-1] ==p[j-1] || p[i-1] == '?'

2. dp[i][j] = dp[i-1][j] || dp[i][j-1] iff p[i-1] =='*'

class Solution {
    public boolean isMatch(String s, String p) {
        if(s==null || p==null) return s==p;
        int m = s.length();
        int n = p.length();
        
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int j = 1; j < n+1; j++){
            
            if(p.charAt(j-1) == '*' && dp[0][j-1])
                dp[0][j] = true; //***************
        } 
        
        for(int i = 1; i < m + 1; i++){
            for(int j = 1; j < n+1; j++){
               
                if(p.charAt(j-1) == '*'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
                else if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?'){
                    dp[i][j] = dp[i-1][j-1];
                }
                
            }
        }
        return dp[m][n];
    }
}