## Saturday, November 29, 2014

### [LeetCode] Wildcard Matching

Implement wildcard pattern matching with support for `'?'` and `'*'`.
```'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false```

p[j-1] == s[i-1] || p[j-1] == '?'：dp[i][j] = dp[i-1][j-1]
p[j-1] == '*'：
1. 匹配0个字符：dp[i][j] = dp[i][j-1]
2. 匹配1个字符：dp[i][j] = dp[i-1][j-1]
3. 匹配多个字符：dp[i][j] = dp[i-1][j]

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17``` ```class Solution { public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vector> dp(m+1, vector(n+1,false)); dp[0][0] = true; for(int i=0; i0 && dp[i-1][j-1]; else if(p[j-1]=='*') dp[i][j] = dp[i][j-1] || (i>0 && (dp[i-1][j-1] || dp[i-1][j])); } } return dp[m][n]; } }; ```

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