yxc题解
参考题解1
参考题解2
P37笔记(ACWing本)有分析状态转移方程
图1
图2
图3
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s, p = ' ' + p; //为了方便让两个字符串下标从1开始,前面都补空格
vector<vector<bool>> f(n + 1, vector<bool> (m + 1));
f[0][0] = true; // 当s与p均为空串
for (int i = 0; i <= n ; i ++)
for (int j = 1; j <= m; j ++) { //j从0开始没有意义(如果i不是0的话),当i=0,j=0已经初始化过了
if (j + 1 <= m && p[j + 1] == '*') continue; // 将~*视为整体去匹配,对于单独的~字符,不用考虑
if (i && p[j] != '*') f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
else if (p[j] == '*') f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
}
return f[n][m];
}
};