# 44. Wildcard Matching

[Link](https://leetcode.com/problems/wildcard-matching/)

**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];
    }
}
```
