5.【记忆化dfs】实现正则表达式匹配

备注：记忆化深搜（ms）类似于动态规划，仅递推顺序相反，dp可解，则ms可解

题目：输入两个字符串s,p，p包含字符“  ‘.’ ,'*'  ”。点可匹配任意一个字符，星号可匹配零个或多个前一个字符。

eg:

s:aaaab

p:a*b

输出：true；

s:b

p:a*b

输出：true；

class Solution {
public:
    vector<vector<int> >match;
    int dfs(string s,string p,int i,int j){
        if (i == s.size()) return j == p.size() ? 1 : -1;
        if (j == p.size()) return i == s.size() ? 1 : -1;
        if (match[i][j] != 0) return match[i][j];
        if(j==p.size()-1||p[j+1]!='*'){
            if(s[i]==p[j]||p[j]=='.'){
                match[i][j]=dfs(s,p,i+1,j+1);
                return match[i][j];
            }
        }
        else{
            if (dfs(s, p, i, j + 2) > 0) {
                match[i][j] = 1;
                return match[i][j];
            }
            if(s[i]==p[j]||p[j]=='.'){
                bool t=dfs(s,p,i+1,j)>0||dfs(s,p,i+1,j+2)>0;
                match[i][j]=t?1:-1;
                return match[i][j];
            }
        }
        match[i][j]=-1;
        return match[i][j];
    }
    bool isMatch(string s, string p) {
        s+='#';
        p+='#';
        match=vector<vector<int> >(s.size(),vector<int>(p.size(),0));
        return dfs(s,p,0,0)>0;
    }
};