模式匹配的实现，'?'代表单一字符，'*'代表随意多的字符。写代码实现两个字符串是否匹配。
Implement wildcard pattern matching with support for '?' and '*'.、
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). The function prototype should be:
bool isMatch(const char *s, const char *p) Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
要注意的就是'*'能够代表随意长度的字符，甚至能够是0个。也就是能够忽略。以下是简单的分析思路：
1）两个辅助指针分别指向模式串和比較字符串，假设当前两个字符相等（可能是'?
'）。两个指针都加一比較下一个字符。
2）假设比較字符串当前字符是星号，由于星号可能代表0个字符或者多个字符，零个字符就代表比較字符串的下一个字符和模式串的当前字符比較，假设不相等。说明不是代表零个字符，这个时候就要用比較字符串的下一个跟模式串的下一个比較。
假设相等说明可能代表零个字符。那么就等于运行了第一步。直到遇到不相等的字符时，说明星号可能代表了较多的字符。而我们仅仅是吃掉了较少的字符。这个时候我们就应该回退到星号的后一个字符，去跟模式串之前标记不相等的位置的后一个去比較。
因此。在遇到星号的时候我们应该标记模式串和比較字符串的位置，当遇到不相等的时候模式串的标记后移一位，说明星号多代表了一个字符。
3）最后比較字符串可能还剩下比較多的星号，应为星号可能代表零个字符，一次要忽略掉这些。
4）最后查看比較字符串是否到尾部就说明两个字符串是否匹配。
代码例如以下：
class Solution {
public:
bool isMatch(const char *s, const char *p) {
const char* star = nullptr;
const char* rs = nullptr;
while(*s) {
if(*s == *p || *p == '?
') { //match
s++; p++;
continue;
}
if(*p == '*') {
star = p; // record star
p++; //match from next p
rs = s; // record the position of s , star match 0，从匹配零个字符開始
continue;
}
if(star != nullptr) { //if have star in front then backtrace
p = star + 1; //reset the position of p
s = rs + 1;
rs ++; //star match 1,2,3,4,5....每次都多吃掉一个字符
continue;
}
return false; //if not match return false，能运行到这步说明发生了不匹配
}
while(*p == '*') p++; //skip continue star
return *p == '\0'; // successful match。之前s已到结尾。看p是否遍历完代表是否匹配
}
};这与之前的一个例题有类似的地方，可是那里的星号是代表了前缀字符，而这里的星号可能代表随意字符数量。
这里的回退与KMP有类似的地方，两者是否能比較融合呢？下次再看到这里的时候要做下比較。