力扣：正则表达式匹配

原题链接
DP：
$\mathrm{f}[\mathrm{i}][\mathrm{j}]$:表示长度 $1-\mathrm{i}$ 的 $\mathrm{S}$ 串与长度 $1-\mathrm{j}$ 的 $\mathrm{P}$ 串是否匹配
①首先将 $\ast$ 字符与前面的字母看作一个整体。
②$\mathrm{p}[\mathrm{j}]\ne \ast$:$\mathrm{f}[\mathrm{i}][\mathrm{j}]$要想成立，则 $\mathrm{S}$ 串前 $\mathrm{i}-1$ 个字符与 $\mathrm{P}$ 串的前 $\mathrm{j}-1$ 个字符匹配，同时满足 $\mathrm{S}$ 串第 $\mathrm{i}$ 个字符与 $\mathrm{P}$ 串第 $\mathrm{j}$ 个字符匹配或者，$\mathrm{P}$ 串第 $\mathrm{j}$ 个字符为 ′.′'.'′.′，即：
f[i][j]=f[i−1][j−1]&&(s[i]==p[j]∣∣p[j]==′.′)\\rm f[i][j] = f[i - 1][j-1] \\&\\&(s[i] == p[j] || p[j] == '.') f[i][j]=f[i−1][j−1]&&(s[i]==p[j]∣∣p[j]==′.′)
③$\mathrm{p}[\mathrm{j}]=\ast$:
$\ast$ 会匹配 $\mathrm{S}$ 串任意多个字符：
1）当 $\ast$ 匹配 $\mathrm{S}$ 串 0 个字符时：由于将 $\ast$ 字符与前面的字母看作一个整体，所以 $\mathrm{S}$ 串的前 $\mathrm{i}$ 个字符与 $\mathrm{P}$ 串的前 $\mathrm{j}-2$ 个字符匹配。
$$\mathrm{f}[\mathrm{i}][\mathrm{j}-2]$$
2）当 $\ast$ 匹配 $\mathrm{S}$ 串 1 个字符时：由于将 $\ast$ 字符与前面的字母看作一个整体，
所以 $\mathrm{S}$ 串的前 $\mathrm{i}-1$ 个字符与 $\mathrm{P}$ 串的前 $\mathrm{j}-2$ 个字符匹配，
$\mathrm{S}$ 串的第 $\mathrm{i}$ 个字符与 $\mathrm{P}$ 串 $\ast$ 前面的字符（即 $\mathrm{j}-1$ 个字符）相等。
$$\mathrm{f}[\mathrm{i}-1][\mathrm{j}-2]\&\&s[\mathrm{i}]==\mathrm{p}[\mathrm{j}-1]$$
2）当 $\ast$ 匹配 $\mathrm{S}$ 串 2 个字符时：由于将 $\ast$ 字符与前面的字母看作一个整体，所以 $\mathrm{S}$ 串的前 $\mathrm{i}-2$ 个字符与 $\mathrm{P}$ 串的前 $\mathrm{j}-2$ 个字符匹配，
$\mathrm{S}$ 串的第 $\mathrm{i}$ 个字符与 $\mathrm{P}$ 串 $\ast$ 前面的字符（即 $\mathrm{j}-1$ 个字符）相等,
$\mathrm{S}$ 串的第 $\mathrm{i}-1$ 个字符与 $\mathrm{P}$ 串 $\ast$ 前面的字符（即 $\mathrm{j}-1$ 个字符）相等。
$$\mathrm{f}[\mathrm{i}-1][\mathrm{j}-2]\&\&\mathrm{s}[\mathrm{i}]==\mathrm{p}[\mathrm{j}-1]\&\&\mathrm{s}[\mathrm{i}-1]==\mathrm{p}[\mathrm{j}-1]$$
以此类推……
得到
$$\mathrm{f}[\mathrm{i}][\mathrm{j}]=\mathrm{f}[\mathrm{i}][\mathrm{j}-2]||f[\mathrm{i}-1][\mathrm{j}-2]\&\&s[\mathrm{i}]==\mathrm{p}[\mathrm{j}-1]||f[\mathrm{i}-1][\mathrm{j}-2]\&\&\mathrm{s}[\mathrm{i}]==\mathrm{p}[\mathrm{j}-1]\&\&\mathrm{s}[\mathrm{i}-1]==\mathrm{p}[\mathrm{j}-1]\dots \dots$$
由该公式知
$$\mathrm{f}[\mathrm{i}-1][\mathrm{j}]=\mathrm{f}[\mathrm{i}-1][\mathrm{j}-2]||\mathrm{f}[\mathrm{i}-2][\mathrm{j}-2]\&\&s[\mathrm{i}-1]==\mathrm{p}[\mathrm{j}-1]||\mathrm{f}[\mathrm{i}-2][\mathrm{j}-2]\&\&\mathrm{s}[\mathrm{i}-1]==\mathrm{p}[\mathrm{j}-1]\&\&\mathrm{s}[\mathrm{i}-2]==\mathrm{p}[\mathrm{j}-1]\dots \dots$$
可得
$$\mathrm{f}[\mathrm{i}][\mathrm{j}]=\mathrm{f}[\mathrm{i}][\mathrm{j}-2]||\mathrm{f}[\mathrm{i}-1][\mathrm{j}]\&\&\mathrm{s}[\mathrm{i}]==\mathrm{p}[\mathrm{j}-1]$$
c++:

class Solution {
public:bool isMatch(string s, string p) {int n = s.size(),m = p.size();s = ' ' + s,p = ' ' + p;vector<vector<bool>> f(n + 1,vector<bool>(m + 1));f[0][0] = 1;for(int i = 0;i <= n;i++){for(int j = 1;j <= m;j++){if(j + 1 < s.size() && p[j + 1] == '*') continue;if(i && p[j] != '*') {f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');}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];}
};