# 44. Wildcard Matching

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FAyPVirwXRzLvIFelyf4f%2F%E5%9C%96%E7%89%87.png?alt=media\&token=1c443484-4a94-4759-87ea-b948f2db3c2d)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FBwpnsGfjTwKwe5qntLM1%2F%E5%9C%96%E7%89%87.png?alt=media\&token=268ca88a-dc09-4d4a-94b6-a339bc2d65f7)

```
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)

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