//dp[i][j] = true if s[0...i-1] match p[0...j-1], 求dp[s.size()][p.size()]

//if p[j-1] == '*', dp[i][j] = dp[i][j-2] || ((p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j]),前者是x* match empty,后者是x*匹配xx*

//else dp[i][j] = dp[i-1][j-1] && ((p[j-1] == s[i-1] || p[j-1] == '.')) && i > 0

int m = (int)s.size(), n = (int)p.size();

auto dp = vector<vector<bool>>(m + 1, vector<bool>(n + 1, false));

dp[0][0] = true;

for (int i = 0; i <= m; ++i) {

for (int j = 1; j <= n; ++j) {

if (p[j-1] == '*') {

//p[0] == '*' make no sense

dp[i][j] = (j >= 2) && (dp[i][j-2] || ((i > 0) && (p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j-1]));

} else {

dp[i][j] = (i > 0) && dp[i-1][j-1] && (p[j-1] == s[i-1] || p[j-1] == '.');

}

}

}

return dp[m][n];