正则表达式匹配

【道德经·第十九章】绝圣弃智，民利百倍；绝仁弃义，民复孝慈；绝巧弃利，盗贼无有。此三者以为文不足，故令有所属；见素抱朴，少私寡欲；绝学无忧。

剑指 Offer 19. 正则表达式匹配

请实现一个函数用来匹配包含’.’和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

class Solution {
public:
    bool isMatch(string s, string p) {
        //指针i，j从索引0开始移动
        return helper(s, 0, p, 0);
    }

    bool helper(string& s, int i, string& p, int j) {
        int n = s.size();
        int m = p.size();
        //模式串匹配完毕，s也匹配完毕：匹配成功
        if(j == m) return i==n;
        // s:a, p:ab*c*
        if(i == n) {
            //如果能匹配成功，一定是字母和*成对出现
            if((m-j)%2 == 1) return false;
            //检查是否为x*y*z*的形式
            for(; j+1 < m; j+=2) {
                if(p[j+1] != '*') {
                    return false;
                }
            }

            return true;
        }

        // 记录状态（i，j）消除重叠子问题
        string key = to_string(i) + "," + to_string(j);
        if(mp.count(key)) return mp[key];

        bool res = false;
        //匹配
        if(s[i]==p[j] || p[j]=='.') {
            //1-1 通配符匹配0次或多次
            if(j+1<m && p[j+1]=='*') {
                res =  helper(s, i+1, p, j) || 
                    helper(s, i, p, j+2);
            } else {
                //1-2 常规匹配一次
                res = helper(s, i+1, p, j+1);
            }
        } else {
            //不匹配
            if(j+1<m && p[j+1]=='*') {
                //2-1 通配符匹配0次
                res =  helper(s, i, p, j+2);
            } else {
                //2-2 无法继续匹配
                res = false;
            }
        }
        //将当前结果记入备忘录
        return mp[key] = res;
    }
private:
    unordered_map<string, bool> mp;
};

位我上者，灿烂星空；道德律令，在我心中。