Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
bool isMatch(string s, string p) {
int len_s = s.size(), len_p = p.size();
bool dp[len_s+1][len_p+1];
//Since the dp[len_s][len_p] means comparison of two empty string, which should be true.
dp[len_s][len_p] = true;
for(int i = len_s; i>= 0; i--){
for(int j = len_p; j>= 0; j--){
//We already set the value to true above;
if(i == len_s && j == len_p) continue;
bool firstMatch = (i<len_s && j< len_p && (s[i] == p[j] || p[j] == '.'));
if(j+1 < len_p && p[j+1] == '*'){
dp[i][j] = dp[i][j+2]|| (firstMatch&&dp[i+1][j]);
}
else
dp[i][j] = firstMatch&&dp[i+1][j+1];
}
}
return dp[0][0];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment