10. 正则表达式匹配

class Solution {
    string s;
    string p;
    vector<vector<int>> f;
    bool dfs(int sidx, int pidx)
    {
        if(f[sidx][pidx] != -1)
            return f[sidx][pidx];
        if(pidx == p.size())
            return f[sidx][pidx] = sidx == s.size();
        bool res1 = (sidx < s.size() && pidx < p.size() && (s[sidx] == p[pidx] || p[pidx] == '.'));
        bool res2;
        if(pidx + 1 < p.size() && p[pidx + 1] == '*')
        {
            bool a = dfs(sidx, pidx + 2);
            bool b = res1 && dfs(sidx + 1, pidx);
            res2 = a || b ;
        }
        else
        {
            res2 = res1 && dfs(sidx + 1, pidx + 1);
        }
        return f[sidx][pidx] = res2;
    }
public:
    bool isMatch(string _s, string _p) {
        s = _s;
        p = _p;
        if(!s.size() && !p.size()) return true;//都没有可以
        f = vector<vector<int>>(s.size() + 1, vector<int>(p.size() + 1, -1));
        return dfs(0, 0);
    }
};

第二次写题代码
要注意的是，没有f来存储之前已经得到的数据就会造成内存超出限制

class Solution {
    vector<vector<int>> f;
    bool dfs(string s, string p, int sidx, int pidx)
    {
        if(sidx <= s.size() && pidx <= p.size() && f[sidx][pidx] != -1) return f[sidx][pidx];
        if(pidx == p.size())
            return sidx == s.size();
        bool a = sidx < s.size() && (s[sidx] == p[pidx] || p[pidx] == '.');
        if(pidx + 1 < p.size() && p[pidx + 1] == '*')
        {
            return f[sidx][pidx] = a && dfs(s, p, sidx + 1, pidx) || dfs(s, p, sidx, pidx + 2);
        }
        return f[sidx][pidx] = a && dfs(s, p, sidx + 1, pidx + 1);
    }
public:
    bool isMatch(string s, string p) {
        f = vector<vector<int>>(s.size() + 1, vector<int>(p.size() + 1, -1));
        return dfs(s, p , 0 , 0);
    }
};