main_dp_bottom_up.cpp

// DP (bottom-up)

#defineEXPR(a) (s[i - 1] == p[a] || p[a] == '.')

classSolution {
public:
boolisMatch(string s, string p) {
int m = s.size(), n = p.size();
 vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
 dp[0][0] = true;
for(int i = 0; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(j > 1 && p[j - 1] == '*')
 dp[i][j] = dp[i][j - 2] ||
 (i > 0 && EXPR(j - 2)) &&
 dp[i - 1][j];
else
 dp[i][j] = i > 0 &&
EXPR(j - 1) &&
 dp[i - 1][j - 1];
 }
 }
return dp[m][n];
 }
};