C++ DP O(mn) Solution with Illustration, Easy to Understand

• Straight forward DP, the key point is to figure out the equation. Transformed is the string p without '*', star is an array to bookkeep stars. The equation(the core of this algorithm) is

``````if(table[i-1][j-1]) // peek upper left
if(transformed[j-1]=='.'||transformed[j-1]==s[i-1])
table[i][j]=true;
if(table[i-1][j]&&star[j-1]) // peek up
if(transformed[j-1]=='.'||transformed[j-1]==s[i-1])
table[i][j]=true;
if(table[i][j-1]&&star[j-1]) // look left
table[i][j]=true;
``````

For example: s is "aaa", p is "ab*a*c*a"
The table looks like

``````         *  *  *
p  a  b  a  c  a
s  T  F  F  F  F  F
a  F  T  T  T  T  F
a  F  F  F  T  T  T
a  F  F  F  T  T  T
``````
``````bool isMatch(string s, string p) {
string transformed;
vector<bool> star;
int i=0;
// Transform
while(i<p.size()) {
if(p[i]!='*')
transformed.push_back(p[i]);
if((i+1)<p.size() && p[i+1]=='*') {
star.push_back(true);
i++;
}
else
star.push_back(false);
i++;
}
// Initialize table
vector<vector<bool>> table(s.size()+1,vector<bool>(transformed.size()+1,false));
int j=1;
table[0][0]=true;
while(j<=transformed.size() && star[j-1])
table[0][j++]=true;
// Fill up table
for(i=1;i<=s.size();i++)
for(j=1;j<=transformed.size();j++) {
if(table[i-1][j-1]) // peek upper left
if(transformed[j-1]=='.'||transformed[j-1]==s[i-1])
table[i][j]=true;
if(table[i-1][j]&&star[j-1]) // peek up
if(transformed[j-1]=='.'||transformed[j-1]==s[i-1])
table[i][j]=true;
if(table[i][j-1]&&star[j-1]) // look left
table[i][j]=true;
}
return table[s.size()][transformed.size()];
}
``````

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