这道题按理来说应该是Regular Expression Matching的简单版，但是测试数据较多较复杂，用普通的dfs会超时，常规dp会超内存，因此需要进行额外的处理。
方法一：DP
常规DP使用二维数组
表示s中前i个字符和p中前j个字符的匹配情况，但其实存在冗余，具体可以观察动态转移方程：
其实当前状态至多与前一轮的状态相关，将i作为外层循环的话，要求解
，只需
，令
表示前一轮(s的前一个位置与p[j+1]的匹配关系)，则动态转移方程可以改为：
简单来看，就是用pre[]替换dp[i][]，因为pre代表的是前一轮的匹配状态。然后每一轮循环进行完之后要更新pre。
代码如下，Runtime: 444 ms：
class Solution {
public:
bool isMatch(string s, string p) {
int len1 = s.size(), len2 = p.size();
bool dp[len2 + 1], pre[len2 + 1];
memset(dp, false, sizeof(dp));
memset(pre, false, sizeof(pre));
pre[0] = true;
for(int i = 0; i < len2; ++i)
pre[i + 1] = p[i] == '*' ? pre[i] : false;
if(len1 == 0)
return pre[len2];
for(int i = 0; i < len1; ++i){
for(int j = 0; j < len2; ++j){
if(p[j] == '*')
dp[j + 1] = pre[j + 1] || dp[j];
else
dp[j + 1] = (p[j] == '?' || p[j] == s[i]) ? pre[j] : false;
}
for(int j = 0; j <= len2; ++j)
pre[j] = dp[j];
}
return dp[len2];
}
};
方法二：贪心
使用递归TLE的主要原因是分支太多，回溯耗时。引起回溯的是‘*’号的匹配，常规dfs中，对每一个‘*’号都进行了扩展（依次匹配0个，1个……），当失配时再回溯到该‘*’号。所以减少回溯的切入点就是减少需要回溯的‘*’号。贪心的思路是：只对最后一个‘*’号进行回溯。每当失配时，只回溯到最近的一个‘*’号，令该‘*’号多匹配一个字符，重新进行匹配。
证明如下：令
为最近的‘*’号，与之对应的是
(显然
已经匹配)。若当前对star的扩展嵌套在前一个‘*’号
的扩展中，设匹配了x个字符，处理到
时失配，需要回溯。则最优解为回溯到star，从
开始重新匹配。假设存在另一个最优解是回溯到，由于失配，所以应该尝试匹配x + 1个字符。假设我们足够幸运，使得
匹配（*号多匹配一个字符），则此时与对应的是。二者得到的结果相同，但后者多付出了一次回溯。因此最优解为：回溯到最近的（last）一个‘*’号。
具体处理方法是：维护两对指针，一对指明s,p开始匹配的位置（该位置处p为'*'号）sbeg/star，一对表示当前匹配的位置s_cur/p_cur。
①若*p_cur == '?' || *p_cur == *s_cur，则当前位置匹配，两个指针都继续右移，++s_cur, ++p_cur
②若*p_cur == '*'，则该‘*’号可以匹配任意个字符，首先从0开始尝试，star = p_cur，sbeg = s_cur，++p_cur（待匹配位置）
③否则失配，需要回溯到上一个'*'号，s_cur = ++sbeg, p_cur = star + 1
代码如下，Runtime: 20 ms：
class Solution {
public:
bool isMatch(string s, string p) {
const char* star = NULL;
const char *s_beg = s.c_str(), *s_cur = s_beg, *p_cur = p.c_str();
while(*s_cur){
if(*p_cur == '?' || *p_cur == *s_cur)
++s_cur, ++p_cur;
else if(*p_cur == '*')
star = p_cur, s_beg = s_cur, ++p_cur;
else if(star)
s_cur = ++s_beg, p_cur = star + 1;
else
return false;
}
while(*p_cur == '*')
++p_cur;
return *p_cur == '\0';
}
};