分析：

* 能够匹配随意个字符，包含0个多个连续的*的作用相当于1个*。* 后无其它字符。则直接匹配出现*p为 *，而*s为字符时。我们有两种选择，一种是跳过*p指示的*。也就是令*匹配0个字符，继续向后匹配。

一种是我们须要用* 匹配多个字符，才干完毕匹配。

* 后有其它字符，则在s串中向后找与该非*字符匹配的字符，若没找到，则不匹配，若找到了。则会有不同的情况。

用s中首次遇到的与p中*后的非*字符匹配 

                   

                    这当然是好的，再看还有一种情况。

             2.不能用S 中首次遇到的与p中*后的非*字符与之匹配。

                   

                 如图所看到的。用s首次的e与p中的e匹配后，继续匹配的过程中发生了不匹配，但事实上s串和p是匹配的，这就是说，要继续扩大 * 的作用域，将e也与* 进行匹配。

                         

          

 可是通过前面的情况，我们发现p和s都跑了，p指向了g。s指向了第二个e。所以要记录下*后面的非*字符的位置。以便在兴许发生不匹配时，又一次进行匹配。 

实现:

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

const char *backtrack_s = NULL;

const char *backtrack_p = NULL;

while (*s) {

//match

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

++s;

++p;

}

//don't match.

else {

//meet *

if (*p == '*') {

//skip multiply *.

while (*p == '*')

++p;

if (*p == '\0')

return true;

//record the next position of *.

backtrack_s = s;

backtrack_p = p;

}

//

else {//注意：推断前面是否出现了*

if (backtrack_p) {

//注意：在当前位置往后推断出现不相等的时候，再又一次回到下一个位置又一次往后比較

//其意义是继续扩大*的作用范围。

s = ++backtrack_s;

p = backtrack_p;//恢复p的位置

}

//既不匹配。前面又没有*，这就是真的不匹配了。

else return false;

}

}

} //end while

while (*p == '*')//处理p末端的*

++p;

return (*s == '\0' && *p == '\0');

}

查看原文