C++ Solution works


#1

int fun(const string A, const string B,int i1,int i2,vector<vector> &dp)
{
if(i1<0&&i2<0)
{
return 1;
}

if(i2<0||i1<0)
{
    return 0;
}

if(dp[i1][i2]!=-1)
{
    return dp[i1][i2];
}


if(A[i1]==B[i2]||B[i2]=='.')
{
    return dp[i1][i2]=fun(A,B,i1-1,i2-1,dp);
}

if(B[i2]=='*')
{
    int ans=fun(A,B,i1,i2-2,dp);
    if(i2>0&&(B[i2-1]=='.'||B[i2-1]==A[i1]))
    {
        ans=ans||fun(A,B,i1-1,i2,dp)||fun(A,B,i1,i2-1,dp);
    }
    return dp[i1][i2]=ans;
}

return 0;

}

int Solution::isMatch(const string A, const string B) {

int n1=A.size(),n2=B.size();
vector<vector<int>> dp(n1+1,vector<int>(n2+1,-1)); 

return fun(A,B,n1-1,n2-1,dp);

}