/**
* DP formulation
* f[i][j] indicate whether s[i..] matches p[j..]
* dp(i, j) calculates f[i][j]
*
* base condition: f[n][m] = true;
* if(s[i]==p[j] || p[j]=='.') f[i][j] = f[i+1][j+1]
* else if(p[j+1] == '*') f[i][j] = s[i]==p[j] && f[i+1][j] || f[i][j+2]
**/
class Solution {
public:
vector<vector<int>> f;
int n, m;
string s, p;
bool isMatch(string _s, string _p) {
s = _s, p = _p;
n = s.size();
m = p.size();
f = vector<vector<int>>(n+1, vector<int>(m+1, -1));
f[n][m] = true;
return f[0][0] = dp(0, 0);
}
bool dp(int x, int y){
if(f[x][y] != -1) return f[x][y];
if(y == m) return f[x][y] = x == n;
int ans;
int first_match = x < n && (s[x]==p[y] || p[y]=='.');
if(y+1<m && p[y+1] == '*')
ans = first_match && dp(x+1, y) || dp(x, y+2);
else
ans = first_match && dp(x+1, y+1);
return f[x][y] = ans;
}
};
技巧
&&的优先级比||高