思路分析
依然是正则表达式，但是数据强了一些，递归的算法虽然很好想写出来很漂亮但是无法通过比较恶心的case，原因是在匹配“*”的时候用到了逐次匹配的思想，让“*”匹配到的字符尽量少，如果一直不成功才会逐渐多地匹配字符，直到最后匹配了整个剩余串。这样如果存在多个“*”的话，就会导致递归开销急剧增大，最终TLE掉。
所以这里我们需要引入一个漂亮的贪心思想来解决问题。首先我们遍历s，对几种可能的状态进行处理：如果当前*s和*p中有一个是问号，或者这两个字符相等，那么两个指针均后移一位，指向下一个字符；如果*p是一个星号通配符，则保存这个星号的位置，以及当前匹配到的位置，并将指针p向后移动一位；这样，当下一次匹配失败的时候，我们就可以有机会直接让先前那个星号多匹配一个字符——星号的定义原本是尽量少地匹配字符，如果我们只在匹配失败的时候才往前回溯让星号多进行匹配，自然会节省大量的递归开销。最后，利用这个巧妙的贪心优化，我们就可以得到一个更高效的匹配算法了。需要注意的一点是，如果最后匹配完了所有的s，但是*p还是非空，则要判断一下剩余的p串是否都是星号。如果是的话，同样可以返回true。
代码
class Solution {
public:
bool isMatch(const char *s, const char *p) {
const char * star = NULL, * pos = s;
while ( *s ) {
if ( *s == *p || *p == '?' ) {
s++; p++;
} else if ( *p == '*' ) {
star = p++;
pos = s;
} else if ( star ) {
s = ++pos;
p = star + 1;
} else {
return false;
}
}
while ( *p == '*' ) p++;
return !(*p);
}
};