# C++ recursive solution and DP solution

• recursive solution:

``````bool isMatch(const char *s, const char *p) {
if(!*p) return !*s;
if(!*s) return *(p+1)=='*' && isMatch(s, p+2);
if(*(p+1)=='*')
return isMatch(s, p+2) || (*s==*p || *p=='.') && isMatch(s+1, p);
else
return (*s==*p || *p=='.') && isMatch(s+1, p+1);
}
``````

DP solution:

``````bool isMatch(const char *s, const char *p) {
const int m=strlen(s), n=strlen(p);
bool arr[m+1][n+1];
fill_n(*arr, (m+1)*(n+1), false);
arr[0][0]=true;
for(int j=2; j<=n; j+=2)
if(arr[0][j-2] && p[j-1]=='*')
arr[0][j]=true;
else
break;
for(int i=1; i<=m; ++i)
for(int j=1; j<=n; ++j)
if(p[j-1]=='*')
arr[i][j]=arr[i][j-2] || arr[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.');
else
arr[i][j]=arr[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
return arr[m][n];
}``````

• to your recursive answer, this input will definetely lead to a TLE:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*

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