1. 题目

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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "cab") → false

2. 思路

第一遍类似的思路，直接采用递归测试的方法，复杂度O(N!)，超时。

第二遍通过在匹配到之后，将当前之后到下一个之前的字符串完全匹配后，在递归测试。匹配两个之间的子串时采用的按位直接比较。主要考虑到这部分回退带来的计算成本应该不是大头。结果还是超时。4超时代码是第二遍的代码。ac的算法：将模式串p用*分割成为多个子串，按序去匹配各个子串。只需要匹配一次，因为每次都是匹配的最前的一个成功匹配，如果前面的匹配后后面的剩下串还匹配不上，匹配第二个子串，后面的后缀也匹配不上的。有几个特殊情况要考虑。

1. 第一个子串要特殊考虑，如果第一个子串不是在之后的，则必须匹配s的起点。比如s="Hi hello world" p="helld"

2. 最后一个子串不在之前，则最后一个子串必须是后缀匹配。但是不能直接在前面的遍历匹配上测试是不是最后的后缀匹配，可能不行，最后一个子串时要找到最后的一个匹配子串。这是可以重新测试一下后缀是否匹配。比如s="aabbb", p="ab"

   这是也有一个场景要考虑，如果前面从来没有过*出现，则这是重新做后缀匹配的话，起点可能不是整个s的起点，因此需要重新测试是否是起点。比如s=“aa” p="a"的场景

3. 代码

耗时：22ms

class Solution {public:    // 将*分割的各个段取出来，按序去查找; 全部成功匹配则ok    bool isMatch(string s, string p) {        if (p.length() == 0) { return s.length() == 0; }        vector
    
      segs = split(p);        /*cout << "s=" << s << "\np=" << p << endl;        for (int i = 0; i < segs.size(); i++) {            cout << i << "=" << segs[i] << " ";        }        cout << endl;*/                int match_first_beg = 0;        int start = match_first_beg;        for (int si = 0; si < segs.size(); si++) {            string& seg = segs[si];            int k = matchNoStar(s, start, seg);            //cout << "i=" << si << " si=" << s.substr(start) << " seg=" << seg << " k=" << k << endl;            if (k == -1) {                return false;            }            if (si == 0) {                match_first_beg = k;            }            start = k + seg.length();        }                //cout << "first_start=" << match_first_beg << " end=" << start <<  " end_str=" << s.substr(start) << endl;        // 如果第一个模式字符不是*，则要求第一次match的必须是s的起点        if (p.length() > 0 && p[0] != '*' && match_first_beg != 0) {            return false;        }        // 如果最后一个字符不是*，则从末尾重新匹配最后一个模式串        if (p.length() > 0 && p[p.length()-1] != '*' && start != s.length()) {            string& last_seg = segs[segs.size()-1];            int k = matchNoStar(s, s.length() - last_seg.length(), last_seg);            if (k == -1) {                return false;            }            // 匹配成功, 如果整个模式串都没有*, 则要求次后缀匹配的起点是整个字符串s的起点            if (segs.size() > 1 || p[0] == '*') { return true; }            else { return false; }        }        return true;    }        vector
     
       split(string& p) {        vector
      
        ret;        int start = 0;        for (int i = 0; i < p.length(); i++) {            if (p[i] == '*') {                if (i > start) {                    ret.push_back(p.substr(start, i-start));                }                start = i + 1;            }        }        if (start < p.length()) {            ret.push_back(p.substr(start));        }        return ret;    }        // 从s[start]开始匹配模式串p, p是不包含*的模式串    int matchNoStar(string& s, int start, string& p) {        int k = start;        int i = start;        int j = 0;        while (i < s.length() && j < p.length()) {            if (s[i] == p[j] || p[j] == '?') {                i++;                j++;                continue;            } else {                i = i - j + 1;                j = 0;                k = i;            }        }        if (j == p.length()) {            return k;        }        return -1;    }};
      
     
    

4. 超时代码

class Solution {public:    bool isMatch(string& s, string& p) {        compress(p); // 连续的*进行压缩, 提升性能        return isMatch2(s, p);    }    // 直接采用递归的方式，由于每个*都需要匹配后续所有的字符，复杂度是O(N!), 会超时。    // 优化是每次匹配到*时，避免继续试探后续所有的后缀组合，    // 而是直接根据模式串*之后的字符先进行查找匹配，    // 对所有找到的匹配串进行递归, 如果匹配不到则fail。    bool isMatch2(string& s, string& p) {        cout << "s=" << s << " p=" << p << endl;        int ls = s.length();        if (ls == 0) {             return matchNull(p);        }        int lp = p.length();        if (lp == 0) { return false; }                int i = 0;        int j = 0;        while  (i < lp && j < ls) {            if (p[i] != '*') {                if (j < ls && (p[i] == '?' || p[i] == s[j])) {                    i++; j++;                    continue;                } else {                    return false;                }            } else {                i++;                if (i == lp) { return true; } // the '*' is the last char in p                while (j < ls) {                    int ki = i;                    int kj = j;                    int in_star_len = 0;                    while (p[ki] != '*' && ki < lp && kj < ls) {  // p的当前*到下一个*或结尾之前是否完全匹配, 找到所有的完全匹配进行试探                        if (p[ki] == '?' || p[ki] == s[kj]) {                            in_star_len++;                            ki++; kj++;                            continue;                        } else { // 部分匹配的情况下 回退后继续                            ki = i;                            kj = kj - in_star_len + 1;                            in_star_len = 0;                        }                    }                    {                        string sj = s.substr(kj);                        string pi = p.substr(ki);                        if (isMatch2(sj, pi)) {  // 递归测试剩下的                            return true;                        } else { // 测试失败, 继续重新查找*--*之间的模式串                            j = kj - in_star_len + 1;                            in_star_len = 0;                            continue;                        }                    }                }                return false;            }        }        return i == lp && j == ls;    }    // 将连续的多个*压缩为一个    void compress(string& p) {        string p2;        char last = 0;        for (int i = 0; i < p.length(); i++) {            char pi = p[i];            if (pi == '*' && last == '*') { continue; }            last = pi;            p2 += pi;        }        p = p2;        return ;    }        bool matchNull(string& r) {        int len = r.length();        if (len == 0) { return true; }        for (int i = 0; i < len; i++) {            if (r[i] != '*') { return false; }        }        return true;    }};