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];}
};
