'?' 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 1. 动态规划
bool isMatch(string s, string p) {
int ls = s.length(), lp = p.length(), i, j;
vector<vector<bool>> dp(, vector<bool>(lp+, ));
bool k = ;
dp[][] = ;
for(i = ; i <= lp; i++)
dp[][i] = dp[][i-] && '*' == p[i-];
for(i = ; i <= ls; i++)
{
dp[k][] = ;
for(j = ; j <= lp; j++)
{
if('*' == p[j-])
dp[k][j] = dp[k][j-] || dp[!k][j];
else
dp[k][j] = dp[!k][j-] && (p[j-] == s[i-] || '?' == p[j-]);
}
k = !k;
}
return dp[!k][lp];
}
2. 不匹配的时候回到上一个星号的地方，使星号多匹配一个字符。
bool isMatch(string s, string p) {
int ls = s.length(), lp = p.length(), last_i = -, last_j = -, i = , j = ;
while(s[i])
{
if('*' == p[j])
{
j++;
if(!p[j])
return ;
last_i = i;
last_j = j;
}
else if(s[i] == p[j] || '?' == p[j])
{
i++;
j++;
}
else if(last_i != -)
{
i = ++last_i;
j = last_j;
}
else
return ;
}
while('*' == p[j])
j++;
return !p[j];
}