# A pattern-based DP solution in C++, best submission 4ms

• ``````class Solution {
public:
bool isMatch(string s, string p)
{
int sLen = s.length(), pLen = p.length();
int match[pLen+1][sLen+1];
memset(match, 0, sizeof(int)*(pLen+1)*(sLen+1));
match[0][0] = 1;
for(int i = 2; i <= pLen; i += 2)
if(p[i-1] == '*') match[i][0] = 1; else break;
for(int i = 1; i <= pLen; ++i)
{
if(p[i-1] == '*')
for(int j = 1; j <= sLen; ++j)
match[i][j] = match[i-2][j] || ((p[i-2]=='.' || p[i-2]==s[j-1]) && match[i][j-1]);
else
for(int j = 1; j <= sLen; ++j)
match[i][j] = match[i-1][j-1] && (p[i-1]=='.' || p[i-1]==s[j-1]);
}
return match[pLen][sLen];
}
};
``````

• A recursive funny solution enclosed here.

``````class Solution
{
private:
bool isMatch(char* s, char* p)
{
if(*p == '\0') return *s == '\0';
if(*(p+1) == '*')
return isMatch(s, p+2) || (*s!='\0' && (*s==*p || *p=='.') && isMatch(++s, p));
else
return (*s!='\0' && (*s==*p || *p=='.') && isMatch(++s, ++p));
}
public:
bool isMatch(string s, string p)
{
char *ss = (char*)s.c_str(), *pp = (char*)p.c_str();
return isMatch(ss, pp);
}
};``````

• I just have no idea why this solution is overlooked since almost all the solutions so far are just `string-based`.

• @LHearen Hi LHearen, thank you for your sharing. I have a question. What does `&& match[i][j-1]` mean in `if(p[i-1] == '*')`? I know `match[i-2][j]` means that `'*'` matches zero, and if `'*'` matches something, we need to see whether `(p[i-2]=='.' || p[i-2]==s[j-1])`, but why we have to add this `&& match[i][j-1])`?

• @zhugejunwei We have to ensure `previous` characters are properly matched not only just the previous one.

• @zhugejunwei Besides we also need to `refer to` its previous `matching` state when matching `one` or `more` using `*`.

• @LHearen Thanks for the explanation. Now I get it.

• @LHearen This is awesome, thanks

• @LHearen I think your recursive solution can be optimized as follows:

``````class Solution {
bool isMatch(char* s, char* p){
if(*p == '\0') return *s == '\0';
if(*(p+1) == '*') return isMatch(s, p+2) ||
(*s!='\0' && (*p=='.' || *s==*p) && isMatch(s+1, p));
else return *s!='\0' && (*p=='.' || *s==*p) && isMatch(s+1, p+1);
}
public:
bool isMatch(string s, string p) {
return isMatch((char*)s.c_str(), (char*)p.c_str());
}
};
``````

• @LHearen All my submissions are just gone, I just done them yesterday. What's happening?!

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