# 44. Wildcard Matching 通配符匹配

``````Given an input string (s) and a pattern (p), 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).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

``````Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
``````

Example 2:

``````Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
``````

Example 3:

``````Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
``````

Example 4:

``````Input:
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
``````

Example 5:

``````Input:
s = "acdcb"
p = "a*c?b"
Output: false
``````

Difficulty: Hard

`?`能替代任何字符,`*`能替代任何字符串.

### 解法1

``````bool isMatch(string s,string p){

char *ss = new char[s.size()+1];
strcpy(ss,s.c_str());
char *pp = new char[p.size()+1];
strcpy(pp,p.c_str());
return isMatch2(ss,pp);

}

bool isMatch2(char *s, char *p) {

/*
scur,pcur 指向当前匹配的字符
sstar 指向连续*中最后的一个位置
pstar 指向此时s的位置
*/
char *scur = s, *pcur = p, *sstar = NULL, *pstar = NULL;
while (*scur) {
// 如果当前字符匹配 则向后进行
if (*scur == *pcur || *pcur == '?') {
++scur;
++pcur;
}
// 如果pcur指向*,则将pcur指向下一个(可能有连续的*),并记录当前的sstar为上一次scur
else if (*pcur == '*') {
pstar = pcur++;
sstar = scur;
}
// 如果之前有遇到过*,取到当前的pcur,和scur
else if (pstar) {
pcur = pstar + 1;
scur = ++sstar;
}
else {
return false;
}
}
while (*pcur == '*') ++pcur;
return !*pcur;
}
``````

### 解法2

``````bool isMatch(string s, string p) {
int m = s.size(),n = p.size();
vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
dp[0][0] = true;
for (int i=1;i<=n;i++){
if (p[i-1]=='*') dp[0][i] = dp[0][i-1];
}
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++){
if (p[j-1]=='*') {
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}else{
dp[i][j] = (s[i-1]==p[j-1]||p[j-1]=='?') && dp[i-1][j-1];
}
}
}

return dp[m][n];
}
``````

http://www.cnblogs.com/grandyang/p/4401196.html