给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.‘ 和 ‘*‘ 的正则表达式匹配。 ‘.‘ 匹配任意单个字符 ‘*‘ 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
输入：s = "aa" p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
输入：s = "aa" p = "a*" 输出：true 解释：因为 ‘*‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a‘。因此，字符串 "aa" 可被视为 ‘a‘ 重复了一次。
输入：s = "ab" p = ".*" 输出：true 解释：".*" 表示可匹配零个或多个（‘*‘）任意字符（‘.‘）。
输入：s = "aab" p = "c*a*b" 输出：true 解释：因为 ‘*‘ 表示零个或多个，这里 ‘c‘ 为 0 个, ‘a‘ 被重复一次。因此可以匹配字符串 "aab"。
输入：s = "mississippi" p = "mis*is*p*." 输出：false
在Alchemist练习之后点开它的Code会发现正则表达式匹配的规则：
const p = pattern.charAt(col - 1); const prev = pattern.charAt(col - 2); if (p === ‘.‘ || p === t) { table[row][col] = table[row - 1][col - 1]; else if (p === ‘*‘) { if (table[row][col - 2] === true) { table[row][col] = true } else if (prev === ‘.‘ || prev === t) { table[row][col] = table[row - 1][col]; } } else { table[row][col] = false; }
这个规则用动态规划可以进行推算：
在Alchemist需要用状态转移方程来进行推算，求出最后的m行n列的状态是否为true并返回，
推算‘*’和‘.’出现的几种不同的情况结合状态转移方程进行判断为本题难点。
假设‘*’在p字符中最后出现：
1.首先查看字符串是否匹配，两个字符串都不匹配的话它直接等于本行前面两个的状态。
2.字符串匹配，本行前面两个的状态为false，需要查看字符是否出现过，并等于上一行的状态。
字符串匹配：
1.字符串匹配并且字符相等的话返回true，字符串匹配字符不等的话返回false。
2.假设‘.‘在字符串最后出现，默认一定返回true
没有‘*‘出现的时候：
1.字符串互相匹配，判断字符是否相等，字符相等返回上一行上一列的状态。
代码：
class Solution { public boolean isMatch(String s, String p) { int m = s.length(); int n = p.length(); boolean[][] f = new boolean [m+1][n+1]; f[0][0]=true; for(int i = 0;i<=m ; i++){ for(int j = 1;j<=n ; j++){ if(p.charAt(j-1) == ‘*‘){ f[i][j]=f[i][j-2]; if(matches(s, p, i, j-1)){ f[i][j] = f[i][j] || f[i-1][j]; } }else{ if(matches(s, p, i, j)){ f[i][j] = f[i-1][j-1]; } } } } return f[m][n]; } public boolean matches(String s,String p,int i,int j){ if(i == 0){ return false; } if(p.charAt(j-1) == ‘.‘){ return true; } return s.charAt(i-1) == p.charAt(j-1); } }
原文：https://www.cnblogs.com/yesimola/p/14727999.html