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

Have you met this question in a real interview? 

Yes

Example

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

感觉很难，不过这是个回答yes or no的two sequence题目，自然而然想到dp， 那么f[i][j]为A取i个，B取j个match的对不对，状态方程来自到底是？*还是正常的。初始化的时候也比较tricky, 分f[0][*]要比较是不是f[0][j-1] &&& b[j-1]=='*'， 这里我做的时候犯了个错误，就是把？也放到里面了，其实是不对的，因为？不cover空串。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: /** * @param s: A string * @param p: A string includes "?" and "*" * @return: A boolean */ bool isMatch(const char *s, const char *p) { // write your code here int m=strlen(s); int n=strlen(p); bool tbl[m+1][n+1]; tbl[0][0]=true; for (int i=1; i<=m; i++) tbl[i][0]= false; for (int j=1; j<=n; j++) tbl[0][j]=tbl[0][j-1] && p[j-1] =='*'; for (int i=1; i<=m; i++){ for (int j=1; j<=n; j++){ char tmp=p[j-1]; if (tmp=='?') tbl[i][j]=tbl[i-1][j-1]; else if (tmp=='*') tbl[i][j]= tbl[i-1][j] || tbl[i][j-1]; else tbl[i][j]= tbl[i-1][j-1] && s[i-1]==p[j-1]; } } return tbl[m][n]; } };