s跟p指针当前位置都是字符的话，没啥好说的，相同就指针后移，不同就失配。

p

指针

当前位置是？的话，直接略过比较，s指针后移。

p

指针

当前位置是*的话，需要尝试不匹配，和匹配多个字符的可能。

这里对*有个策略

比如：

ababaaab a*b*b

p中的*b*有两种匹配可能

第一种：

ababaaab

*b*

第二种：

ababaaab

  *b* 这两种都是正确解，而本题只要判断是否匹配即可

所以*号可以按正则里的最少匹配策略来

而且最重要的一点*b*中，假如*b找到了可能的匹配，后续处理中左边的*不需要做任何的回溯，因为右边的*能匹配掉所有之前失配的字符串，简单来说就是只管回溯最右边的*。

不过这方法还是O（NM）复杂度的，但数据比较弱，可以过。

比如：

aaaaaaaaaaaaaaaaaaaaaa *aaaaaaaaab*

每次碰到p串中的b都会回溯，然后*吃掉s串中一个a字符，继续匹配。只要s串或者p串的a足够长，仍然会TLE。

class Solution {

public:

bool isMatch(const char *s, const char *p) {

const char* pre_star = NULL;

const char* pre_s = s;

for (; *s; ) {

if (*p == *s || *p == '?') {

s ++;

p ++;

}

else if (*p == '*') {

pre_star = p ++;

pre_s = s;

}

else if (pre_star) {

p = pre_star + 1;

s = ++ pre_s;

}

else

return false;

}

for (; *p == '*'; p ++) ;

return *p == 0;

}

};