A well explained dynamic programming C++ solution! 4ms!

• ``````bool isMatch(string s, string p) {
// Dynamic programming
// table[i][j] tells whether s[0:i-1] and p[0:j-1] matches
// table[0][0] = true;
// Case 1: p[j-1] != '*', table[i][j] = (i>0) && (p[j-1] == s[i-1] || p[j-1] == '.') && table[i-1][j-1]; (p cannot match empty, i.e. i > 0)
// Case 2: p[j-1] == '*', denote 'x' = p[j-2].
//         Case 2.1: 'x' matches 0 times in the tail of s: table[i][j] = table[i][j-2] (omit "x*" in p);
//         Case 2.2: 'x' matches at least 1 times in the tail of s: table[i][j] =(i > 0)&&(s[i-1] == p[j-2] || p[j-2] == '.') && table[i-1][j] (omit s[i-1] in s);
const size_t n = s.size();
const size_t m = p.size();
bool table[n+1][m+1] = {0};
table[0][0] = 1;
for(int i = 0; i <= n; i++){
for(int j = 1; j <= m; j++){
if(p[j-1] != '*') table[i][j] = (i>0) && (p[j-1] == s[i-1] || p[j-1] == '.') && table[i-1][j-1];
else table[i][j] = (table[i][j-2]) || ((i > 0)&&(s[i-1] == p[j-2] || p[j-2] == '.') && table[i-1][j]);
}
}
return table[n][m];
}``````

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