10. 正则表达式匹配：给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.‘ 和 ‘*‘ 的正则表达式匹配。

题目描述给你一个字符串 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 s.length 201 p.length 30s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母以及字符 . 和 *。保证每次出现字符 * 时前面都匹配到有效的字符思路使用动态规划思想实现设置一个boolean类型二维数组table[row][col]数据里面存放是当前位置的字符串是否匹配table[row][col] 对应标准 DP 定义dp[i][j] 表示原字符串 s 的前 i 个字符对应 s[0…i-1]与模式串 p 的前 j 个字符对应 p[0…j-1]是否能够匹配。多出来的第 0 行、第 0 列对应空字符串的边界场景dp[0][0]s 为空、p 为空天然匹配值为 truedp[i][0]s 非空、p 为空一定不匹配全为 false布尔数组默认值就是 false无需额外初始化dp[0][j]s 为空、p 非空只有靠 * 消除字符才能匹配需要单独初始化边界初始化第一行s 为空串时判断 p 能否匹配空串。dp[0][0] true空对空基准条件遍历模式串 p如果当前字符 p[j-1] 是说明可以抹掉前一个字符。能否匹配空串取决于抹掉这两个字符后的模式串能否匹配空串 → dp[0][j] dp[0][j-2]*如果是普通字符或 .无法匹配空串直接为 false情况 1当前字符直接匹配普通字符相等或 p 当前是 .逻辑当前两个字符已经匹配上了那么「前 i 个 s 和前 j 个 p 是否匹配」完全取决于「去掉当前字符后前 i-1 个 s 和前 j-1 个 p 是否匹配」。方程dp[i][j]dp[i−1][j−1]dp[i][j] dp[i-1][j-1]dp[i][j]dp[i−1][j−1]情况 2p 当前字符是 *拆成匹配 0 次和匹配多次两个子场景只要任意一种场景成立当前状态就为 true。子场景 2.1* 让前面的字符出现 0 次逻辑相当于把 p 里的「前一个字符 *」这两个字符直接删掉不匹配任何 s 的字符。此时能否匹配取决于s保持不变p 去掉这两个字符后的结果→ 也就是 dp[i][j-2]举例s “a”p “ab*”b* 让 b 出现 0 次p 等价于 “a”此时 dp[1][3] dp[1][1]j-21。子场景 2.2* 让前面的字符出现至少 1 次递推过程匹配 n 次的结果由匹配 n-1 次的结果推导而来。逻辑s 的当前字符已经被 * 匹配掉了此时能否匹配取决于s 去掉当前字符p 保持不变的结果 → 也就是 dp[i-1][j]。举例s “aaa”p “a*”匹配第三个 a 时前两个 a 已经和 a* 匹配了dp[2][2] true第三个 a 继续被 * 匹配因此 dp[3][2] dp[2][2]。公式dp[i][j]{dp[i][j−2]匹配0次无条件尝试或dp[i−1][j]匹配多次前提prev与s当前字符匹配dp[i][j] \begin{cases} dp[i][j-2] \quad \text{匹配0次无条件尝试} \\ \quad \text{或} \\ dp[i-1][j] \quad \text{匹配多次前提prev与s当前字符匹配} \end{cases}dp[i][j]⎩⎨⎧​dp[i][j−2]匹配0次无条件尝试或dp[i−1][j]匹配多次前提prev与s当前字符匹配​具体如下图所示列代表的字符串 s行代表的是字符规律 p首先添加第一列的状态如下TFFFFFFFF这一步在代码中不是这样的顺序这样说是方便理解代码中是想添加第一行的数据第一列是在和非第一行的数据添加时一起添加的然后添加第一行的状态最后根据第一行和第一列去添加非第一行和第一列的表格内容最终结果如下图红框代表的是不同情况下确定状态的情况代码classSolution{//字符串 s 和一个字符规律 ppublicbooleanisMatch(Strings,Stringp){//定义一个二维数组存放对比后的状态//s.length() 1 行//p.length() 1 列booleantable[][]newboolean[s.length()1][p.length()1];//空和空是匹配的为truetable[0][0]true;//col是列columnrow是行//table[0].length获取列数//这个for循环为了初始化第一行的数据for(intcol1;coltable[0].length;col){//数组下标从零开始charchp.charAt(col-1);//此时第一列/行需要匹配的字符串s内容是没有的为空//所以不为*的全是falseif(col1){//大于1的目的是防止-2出错if(ch*){table[0][col]table[0][col-2];}else{table[0][col]false;}}else{if(ch*){table[0][col]true;}else{table[0][col]false;}}}//table.length获取行数//这个for循环是为了添加非第一行的所有数据的for(introw1;rowtable.length;row){//数组下标从零开始charch1s.charAt(row-1);//table[row].lengt获取当前行的列数for(intcol1;coltable[row].length;col){charch2p.charAt(col-1);if(ch1ch2||ch2.){//当前字符匹配//匹配的话就需要去对比其右上角的数据table[row][col]table[row-1][col-1];}elseif(ch2*){if(col1){if(table[row][col-2]){table[row][col]true;// * 前面的字符出现0次}else{charprevp.charAt(col-2);if(prevch1||prev.){table[row][col]table[row-1][col];// * 前面的字符出现多次}}}}}}//获取的是最后一行的最后一个数据所有返回这个数据即可returntable[table.length-1][table[0].length-1];}}代码说明见注释。。。