Implement wildcard pattern matching with support for '?' and '*'.

 

DP:

dp[i][j] = 1 表示s[1~i] 和 p[1~j] match。

则：

if p[j] == '*' && (dp[i][j-1] || dp[i-1][j]) 

dp[i][j] =  1 

else p[j] = ? || p[j] == s[i]

dp[i][j] = dp[i-1][j-1];

else dp[i][j] = false;

 

1 bool isMatch(const char *s, const char *p) { 2         const char *position = NULL; 3         const char *sp = NULL; 4  5         while (*s) { 6             if (*s == *p || *p == '?') { 7                 s++;  8                 p++; 9             }10             else if (*p == '*') {11                 position = p;12                 p++;13                 sp = s;14             }15             else if (position) {16                 p = position + 1;17                 s = ++sp;18             }19             else return false;20         }21 22         while (*p == '*') p++;23 24         return *p == '\0'; 25     }