如果没有 * 这样的特殊字符，实际上双指针匹配就可以满足要求了
但是因为 * 会匹配零次或多次，所以每个位置可能会有多个匹配方式了，因此匹配的时候我们会需要去看前面的子串能否匹配，以及据此来决定这个位置的匹配形式
这就有些类似于 DP 的状态转移形式了
因为题目要求是能否被完全匹配，以及结合之前双指针的思路我们还是需要知道现在匹配到哪了
于是定义 dp[i][j]，最终答案就是 dp[n][m]
不过最好不要用下标，因为可能有空串的情况
现在考虑转移
这里我们仍然从双指针的角度出发
也就是我们现在在 i-1, j-1，要看（转移到） i，j
因此如果 p[j-1] 是一般字符（包括 .），那么取决于 p[j - 1] 是否等于 s[i - 1]
如果是 *
那么分情况讨论，如果是匹配 0 次，那么相当于把这个字符删除了，那么我们看 [j - 2] 的匹配情况
若至少匹配一次，那么必须能和现在的 s[i - 1] 相等
且这次匹配后，j 是不会继续移动的
class Solution {
public:bool isMatch(string s, string p) {int n = s.size();int m = p.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));dp[0][0] = 1;for (int j = 2; j <= m; j++) {if (p[j - 1] == '*') {dp[0][j] = dp[0][j - 2];}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (p[j - 1] != '*') {if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {dp[i][j] = dp[i - 1][j - 1];}} else {dp[i][j] = dp[i][j - 2];if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {dp[i][j] |= dp[i - 1][j];}}}}return dp[n][m];}
};