LeetCode Wildcard Matching

大家好，欢迎来到IT知识分享网。

最近刷LeetCode遇到Wildcard Matching这个题目，与前面的第十题很相似，但是字符*作用扩大让这道题变得很有趣，解法也有很多。
题目：
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

题目理解起来很简单，大概就是字符匹配之类的，具体的解法很多仁兄的博客里面也提了很多种，从递归到动态规划，很详细。本人写完之后看了一下已提交的运行时间很靠前的一位大神的代码，觉得很有意思，所以想记录一下那个人的思路。
先上代码

bool isMatch(string s, string p) {
        int i = 0, j = 0;
    int prevp = -1, prevs = -1;
    while (i < s.size()) {
        if (s[i] == p[j] || p[j] == '?') {
            i++;
            j++;
        }
        else if (p[j] == '*') {
            prevp = j++;
            prevs = i;
        }
        else if (prevp != -1) {
            j = prevp + 1;
            i = ++prevs;
        }
        else {
            return false;
        }
    }
    while (j < p.size() && p[j] == '*') j++;
    return (j == p.size());
    }

这位仁兄的思路就是用i,j作为两个字符串的下标，prevp为出现‘*’时上一次p字符停留的位置，prevs即为上一次s字符停留的位置。这位仁兄最精髓的地方应该就是几个判断的顺序，大概为：
1、如果索引的两个字符相同或者p上为?，则直接跳过；
2、如果索引的两个字符，p上为 * ，那么记录下此时p的索引位置，先将 *代表空字符处理，继续匹配；
3、如果发现匹配不上了，先看看前面有没有 *，有的话回到前面记录的位置，让　＊多表示一位字符，重新匹配；
４、如果发现匹配不上了，前面＊也处理完了，就返回false。
这种思路将判断顺序很巧妙的进行组合，很佩服。