Easy and concise C++ DP solution beats 97.43%

• ``````class Solution {
public:
bool isMatch(string s, string p) {
if (p.empty())
return s.empty();
bool T[p.size() + 1][ s.size() + 1];
//T[i][j] == true means the last i characters of p match the last j characters of s.
for(int i = 0 ; i <= p.size() ; i++)
for(int j = 0 ; j <= s.size() ; j ++)
T[i][j] = false;
T[0][0] = true;
for(int i = 0; i <= p.size() - 1; i++){
for(int j = 0; j <= s.size(); j++){
if(T[i][j] == false)
continue;
else if(i+1 <= p.size() && j+1 <= s.size() && (p[p.size() - 1 -i] == s[s.size() - 1 -j] || p[p.size() -1 - i] == '.'))
//if the next character of p equals the next character of s || the next character of p is '.'
T[i+1][j+1] = true;
else if(i+2 <= p.size() && p[p.size() - 1 -i] == '*' ){
//if the next character of p is '*'
T[i+2][j] = true;
int k = 1;
while(j+k <= s.size() && (s[s.size() - k -j] == p[p.size() - i -2] || p[p.size() - i -2] == '.')){
//if the next charater of s equals the character before '*' of p
T[i+2][j+k] = true;
k++;
}
}
}
}
return T[p.size()][s.size()];
}
};
``````

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