My 4ms C++ DP solution (another recursive version also given 72ms)

• Just to build a DP table checked, where checked[i][j] indicates whether s[0..i-1] matches with p[0..j-1]. The recursive relationship is as below:
To match with the empty string s[0..0] (i.e. to make checked[0][j]), P[0..j-1] has to meet: p[j-1]=='*' (to cancel p[j-2]) and checked[0][j-2] == true;
To match with the string s[0..i-1] (i.e. to make checked[i][j]), P[0..j-1] has to meet:

1. if p[j-1] =='*', then j must be larger than 1 (j>1) and
• checked[i][j-2] (i.e. p[j-2] cancelled by '*')
• checked[i-1][j] && (s[i-1] ==p[j-2] || p[j-2] =='.') (s[i-1] matches with p[j-2] or '.', )
1. if p[j-1] !='*', checked[i-1][j-1] && (s[i-1] ==p[j-1] || p[j-1] =='.')(i.e. s[i-1] matches with p[j-1] or '.')

class Solution {

``````    public:
bool isMatch(string s, string p) {
int sSize = s.size(), pSize = p.size(), i, j;
bool checked[sSize+1][pSize+1];
//        fill_n(&matched[0][0], (sSize+1)*(pSize+1), false);

for(j=2, checked[0][0]=true, checked[0][1]= false; j<=pSize; ++j) // match s[0..0]
checked[0][j] = p[j-1] == '*'? checked[0][j-2]  : false;
for(i=1; i<=sSize; ++i)
for(j=1, checked[i][0]=false; j<=pSize; ++j)
{
if(p[j-1]=='*') // case (1)
checked[i][j] = (j>1) && ( checked[i][j-2]  || ( ( checked[i-1][j]) && (s[i-1]== p[j-2] || p[j-2] == '.')) );
else // case (2)
checked[i][j] = checked[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
}
return checked[sSize][pSize];
}
};
``````

A recursive version, divide cases into two groups (if the next p char is '*' or not)

``````class Solution {
private:
bool helper(const string &s, const string &p, int sS, int pS)
{
int sSize = s.size(), pSize = p.size(), i, j;
if(pS==pSize) return sS ==sSize; // if p goes to its end, then only if s also goes to its end to return true;

if(p[pS+1]!='*')
{
if( sS<sSize && (p[pS]==s[sS] || p[pS] == '.')) return helper(s, p, sS+1, pS+1);
}
else
{
if(helper(s, p, sS,pS+2)) return true;
while(sS<sSize && (p[pS]==s[sS] || p[pS] == '.')) if(helper(s,p, ++sS, pS+2)) return true;
}
return false;
}

public:
bool isMatch(string s, string p) {
helper(s, p, 0, 0);
}
};``````

• For the case 1 in dp solution, there can be only two checks:

1). (j>1) && checked[i][j-2] --when star * doesn't consume any chars in s

2). (j>1) && checked[i-1][j] && (s[i-1]== p[j-2] || p[j-2] == '.') --when star * consume at lease one char in s

• You are right, it can be simplifed. Thanks

• why you can do this without malloc:
bool checked[sSize+1][pSize+1];

• Your dynamic programming code fails for
string aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
pattern a**************************************************************************************
and similar type cases.

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