1.题目解析

题目来源：10.正则表达式匹配——力扣

测试用例

2.算法原理

首先了解题目中的'*'，该字符相当于模仿者，所以必须有一个本体供其模仿，并且该字符与本体合体后呈现出的是原来本体的n个连续字符，当n=0就呈现出空字符串

1.状态表示

此时需要将两字符串分不同区间进行判断，也就是使用布尔类型的二维dp表来存储两个字符串所对应的匹配关系，即

dp[i][j]: s字符串的 [0,i] 区间是否在p字符串的 [0,j] 区间完全匹配

2.状态转移方程

此时我们以p字符串的最后一个位置为突破口判断对应的三种情况并分类讨论，这里需要注意当最后一个位置为'*'时还要继续判断p[j-1]是'.'还是普通字符，再次分类讨论，具体思路如下：

3.初始化

这里为了填表方便开辟了虚拟位置，初始化时就需要对虚拟位置进行特殊处理，这里的虚拟位置就是当两个字符串为空串时的特殊情况

4.填表顺序

由状态转移方程可以知道填表时需要用到上面及左边的表内的值，所以需要从上向下填表，每一行需要从左到右填表

5.返回值

根据状态表示直接返回dp[m][n]即可

3.实战代码

代码解析

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        s = ' ' + s;
        p = ' ' + p;
        dp[0][0] = true;
        for (int j = 2; j <= n; j += 2) {
            if (p[j] == '*') {
                dp[0][j] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j] == '*') {
                    dp[i][j] =
                        dp[i][j - 2] ||
                        (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
                } else {
                    dp[i][j] =
                        (p[j] == '.' || p[j] == s[i]) && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};