题目

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

分析

本来想用递归搜索做，奈何时间复杂度太高，不断超时。递归的代码倒是很好看，辛辛苦苦写的，也贴一下吧=_=

class Solution {
public:
    bool isMatch(string &s, string &p) {
        return solve(s, p, 0, 0);
    }
private:
    bool solve(string &s, string &p, int i, int j){
        if(i==s.size() && j==p.size()) return true;
        if(i==s.size() && p[j]=='*') return solve(s, p, i, j+1);
        if(i==s.size() || j==p.size()) return false;
        if(s[i]==p[j] || p[j]=='?')
            return solve(s, p, i+1, j+1);
        if(j<p.size() && p[j]=='*'){
            while(j<=p.size() && p[j]=='*')
                j++;
            while(i<=s.size()){
                if(solve(s, p, i, j))
                    return true;
                i++;
            }
        }
        return false;
    }
};

接下来是阅读答案的代码。不得不说，代码很简洁，但是感觉很复杂，看了很久也没弄清楚。但是这个过程给了我一些启发：

• 连续的若干''可以简化为一个''
• '*'将字符串p分为若干段
• 这若干段中，第一段需要从s的开头开始匹配，最后一段需要匹配到s的结尾，中间每段只要在s中不重叠地依次出现即可（首段和尾段可以为空）
• 对于'?'的处理可以放在匹配的部分

所以我的方法是：

• 首先预处理，根据'*'的位置将p分为若干段
• 处理首段（如果有的话）
• 处理中间段（如果还没结束的话）
• 处理尾段（如果有的话）

而对于匹配的部分，我使用的是朴素的匹配方法，如果引入更高级的方法能够进一步降低时间复杂度。

实现

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();
        const char *pc=p.c_str();
        vector<pair<int, int>> strinfo; //(start pos, size)
        int i=0;
        while(i<p.size()){//get strinfo
            if(p[i]=='*'){
                while(i<p.size() && p[i]=='*')
                    i++;
            }
            int count = 0, pos = i;
            while(i<p.size() && p[i]!='*'){
                i++; count++;
            }
            strinfo.push_back(make_pair(pos, count));
        }
        int j=0, pos=0, rlt;
        if(strinfo[j].first==0){//start
            rlt = myfind(s, pc+strinfo[j].first, pos, strinfo[j].second);
            if(rlt==string::npos || rlt!=0) return false;
            pos = rlt + strinfo[j].second;
            j++;
        }
        if(j==strinfo.size()) return pos==s.size();
        while(j<strinfo.size()){//mid
            rlt = myfind(s, pc+strinfo[j].first, pos, strinfo[j].second);
            if(rlt==string::npos) return false;
            pos = rlt + strinfo[j].second;
            j++;
        }
        if(strinfo[j-1].second==0)//end
            return true;
        if(pos==s.size()) return true;
        rlt=myfind(s, pc+strinfo[j-1].first, s.size()-strinfo[j-1].second, strinfo[j-1].second);
        return rlt!=string::npos;
    }
private:
    int myfind(const string &s, const char* p, int pos, int n){
        if(n==0) return pos;
        int i=pos, j=0;
        while(i<s.size()){
            if(s[i]==p[j] || p[j]=='?'){
                i++; j++;
                if(j==n) return pos;
            }
            else{
                pos++;
                i=pos; j=0;
            }
        }
        return string::npos;
    }
};

思考

有时候追求代码的简洁会浪费很多时间，而且可读性也不一定好。
与其纠结于使用漂亮的代码，不如先理清思路，然后按部就班地进行，更加稳妥。