# 9ms DP solution with clear steps and cases

• ``````class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<bool>> T(s.size()+1, vector<bool>(p.size()+1, false)); // All "false" by default
T[0][0] = true; // if both strings are empty result is "true"
for(int j = 2; j <= p.size(); j++) { // The s is empty but p has at least two characters
if(p[j-1] == '*') T[0][j] = T[0][j-2];
}
for(int i = 1; i <= s.size(); i++) { // i == 0 was handled so start at 1
for(int j = 1; j <= p.size(); j++) { // j == 0 was handled so start at 1
if(p[j-1] == '.' || p[j-1] == s[i-1]) T[i][j] = T[i-1][j-1]; // Simple case: characters match or p has '.'
else if(p[j-1] == '*') { // complicated case: p has '*'
if(T[i][j-2]) T[i][j] = T[i][j-2]; // '*' and its preceding char. match with 0 chars in s
else if(s[i-1] == p[j-2] || p[j-2] == '.') T[i][j] = T[i-1][j]; //Preceding char match the current char in s
}
}
}
return T[s.size()][p.size()];
}
};

``````

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