Regular Expression Matching

/*
Check for wildcard string matching,Both problem is similar
Question:
'.' can match with any character
'a*' can match with '','a','aa','aaa','aaaa' etc.
*/

bool fun(string s,string p,int i,int j,vector<vector<int>> &dp){
    if(i<=0 && j<=0) return true;
    if(j<=0) return false;
    if(dp[i][j]!=-1) return dp[i][j];
    int ans=0;
    if((i>0 && s[i-1]==p[j-1] ) ||(i>0 && p[j-1]=='.'))  //for second condition we are also adding i>0 because . should matched with some character.
            ans=fun(s,p,i-1,j-1,dp);
    else if(p[j-1]=='*'){
        ans=fun(s,p,i,j-2,dp);
        if((i>0 && j>1 && s[i-1]==p[j-2]) ||(i>0 && p[j-2]=='.'))
                ans=ans || fun(s,p,i-1,j,dp);
        }
    dp[i][j]=ans;
    return ans;

}


class Solution {
public:
    bool isMatch(string s, string p) {
        vector <vector <int>> dp(s.size()+1,vector <int>(p.size()+1,-1));
        return fun(s,p,s.size(),p.size(),dp);
    }
};