10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2:
输入：s = “aa”, p = “a*”
输出：true
解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串“aa” 可被视为 ‘a’ 重复了一次。
示例 3：
输入：s = “ab”, p = “."
输出：true
解释：".” 表示可匹配零个或多个（‘*’）任意字符（‘.’）。
1.状态表示*
dp[i][j] 表⽰：字符串 p 的 [0, j] 区间和字符串 s 的 [0, i] 区间是否可以匹配
2.状态转移方程
⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：
1. i. 当 s[i] == p[j] 或 p[j] == '. ’ 的时候，此时两个字符串匹配上了当前的⼀个字符，只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i][j - 1] ；
ii. 当 p[j] == ‘*’ 的时候，此时匹配策略有两种选择：
• ⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态 dp[i] [j - 1] ，此时 dp[i][j] = dp[i][j -1] ；
• 另⼀种选择是： * 向前匹配 1 ~ n 个字符，直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 1] (0 <= k <= i) 中所有匹配情况中，选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；
1. iii. 当 p[j] 不是特殊字符，且不与 s[i] 相等时，⽆法匹配。 三种情况加起来，就是所有可能的匹配结果。
综上所述，状态转移⽅程为：
▪ 当 s[i] == p[j] 或 p[j] == ‘?’ 时： dp[i][j] = dp[i][j - 1] ；
▪ 当 p[j] == ‘*’ 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ；
3. 初始化
由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。
由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。
dp[0][0] 表⽰两个空串能否匹配，答案是显然的，初始化为 true 。
第⼀⾏表⽰ s 是⼀个空串， p 串和空串只有⼀种匹配可能，即 p 串全部字符表⽰为"任⼀字符+*"，此时也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为"任⼀字符+"的 p ⼦串和空串的 dp 值设为 true 。
第⼀列表⽰ p 是⼀个空串，不可能匹配上 s 串，跟随数组初始化即可
4. 填表顺序
根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右
5. 返回值
返回 dp[m][n]
代码：
bool isMatch(string s, string p) { int n=s.size(); int m=p.size(); //表示的是 s串中0~i 位置的子串，能否于 p串 0~j 上完全匹配 vector<vector<bool>> dp(n+1,vector<bool>(m+1,false)); //初始化 dp[0][0]=true; for(int i=2;i<=m;i+=2)//初始化有坑 { if(p[i-1]=='*') dp[0][i]=1; else break; } //填表 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i-1]==p[j-1]||p[j-1]=='.') { dp[i][j]=dp[i-1][j-1]; } if(p[j-1]=='*') { if(p[j-2]=='.') { dp[i][j]=dp[i][j-2]||dp[i-1][j]; } else { if(p[j-2]==s[i-1])//相等的时候， dp[i][j]=dp[i][j-2]||dp[i-1][j]; //当不相等的时候，也需要考虑匹配空串的情况 else dp[i][j]=dp[i][j-2]; } } } } return dp[n][m]; }
