时间复杂度O(mn),dp[i][j] 代表字符串s的前i个字符和字符串p的前j个字符是否匹配，可以匹配两个字符串均包含通配符的情况
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
if(s == NULL && p == NULL){
return true;
}
if(s == NULL || p == NULL){
return false;
}
int sl = (int)strlen(s);
int pl = (int)strlen(p);
//bool dp[][] = new bool[sl+1][pl+1];
bool dp[sl+1][pl+1];
for(int i = 1; i <= sl; ++i){
for(int j = 1; j <= pl; ++j){
dp[i][j] = false;
}
}
dp[0][0] = true;
for(int i = 1; i <= sl; ++i){
if(dp[i-1][0] == true && s[i-1] == '*'){
dp[i][0] = true;
}else{
dp[i][0] = false;
}
}
for(int i = 1; i <= pl; ++i){
if(dp[0][i-1] == true && p[i-1] == '*'){
dp[0][i] = true;
}else{
dp[0][i] = false;
}
}
for(int i = 1; i <= sl; ++i){
for(int j = 1; j <= pl; ++j){
if(s[i-1] == '*' || p[j-1] == '*'){
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}else if(s[i-1] == '?' || p[j-1] == '?'){
dp[i][j] = dp[i-1][j-1];
}else {
dp[i][j] = ((s[i-1] == p[j-1] ? true : false) && dp[i-1][j-1]);
}
}
}
// cout << dp[sl-1][pl-1] << endl;
return dp[sl][pl];
}
};
