# Simple to understand recursive and DP solutions in C++

• DP Solution :

``````bool isMatchDP(string s, string p)
{
bool dp[s.length()+1][p.length()+1];
memset(dp,0,sizeof(dp));

dp[0][0]=1;
for (int i = 1; i <= s.length(); ++i)
dp[i][0]=0;
for (int j = 1; j <= p.length(); ++j)
{
if(p[j-1]=='*')
dp[0][j] = dp[0][j-2];
else
dp[0][j]=  0;
}

for (int i = 1; i <= s.length(); ++i)
{
for (int j = 1; j <= p.length(); ++j)
{
dp[i][j]=0;
if(s[i-1] == p[j-1] || p[j-1]=='.')
dp[i][j] =  dp[i-1][j-1];
else if( p[j-1]=='*')
{
if(dp[i][j-2] == 1)
dp[i][j]=1;
else if (s[i-1] == p[j-2] || p[j-2]=='.')
dp[i][j] = dp[i-1][j];
}
}
}
return dp[s.length()][p.length()];
}
``````

Recursive Solution :

``````bool isMatch(char* s, char* p)
{
if(p[0]=='\0'){
if(s[0]=='\0')
return true;
return false;
}

if(s[0]=='\0'){
if(p[1]=='*')
return isMatch(s,p+2);
return false;
}

if(p[1]=='*')
{
if( isMatch(s,p+2) )
return true;
if(s[0]==p[0] || p[0]=='.')
return isMatch(s+1,p);
}

if(s[0]==p[0] || p[0]=='.')
return isMatch(s+1,p+1);

return false;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.