44. Wildcard Matching

Similar to problem of regular expression matching. But now '*' can matches empty or everything.
Let dp[i][j] be true if s[0...i-1] matches p[0...j-1]. So there are two cases:

Case 1: p[j-1] != '*'
dp[i][j] == dp[i-1][j-1] (s[0...i-2] matches p[0...j-2]) && s[i-1] matches p[j-1]

Case 2: p[j-1] == '*'
dp[i][j] == dp[i][j-1] (s[0...i-1] matches p[0...j-2] so p[j-1] i.e. '*' matches empty) || dp[i-1][j] ('*' matches everything so far, i.e. p starts with '*') (I made a mistake this place where I thought it should be dp[i-1][j-1])

1:  class Solution {  
2:  public:  
3:    bool isMatch(string s, string p) {   
4:      int m = s.length(), n = p.length();  
5:      vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));  
6:      dp[0][0] = true;  
7:      for (int j = 1; j <= n; j++) {  
8:        dp[0][j] = p[j-1] == '*' && dp[0][j-1];  
9:      }  
10:      for (int i = 1; i <= m; i++) {  
11:        for (int j = 1; j <= n; j++) {  
12:          if (p[j - 1] != '*')  
13:            dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || '?' == p[j-1]);  
14:          else  
15:            dp[i][j] = dp[i-1][j] || dp[i][j-1];  
16:        }  
17:      }  
18:      return dp[m][n];   
19:    }  
20:  };