动态递归之正则表达式

題目：正则表达式

题解

方法一：带记忆化递归

思路：
递归函数 match(i, j) 表示字符串 s 从 i 开始到末尾的子串和模式 p 从 j 开始到末尾的子串是否匹配。
考虑以下情况：

• 如果 j 已经到达 p 的末尾，那么只有当 i 也到达 s 的末尾才匹配成功。
• 首先检查当前第一个字符是否匹配：first_match = (i < s.length()) 且 (s.charAt(i) == p.charAt(j) 或 p.charAt(j) == ‘.’)
• 如果下一个字符是 ‘*’ (即 j+1 < p.length() 且 p.charAt(j+1)==‘*’)，那么有两种情况：
        a. 匹配0个前面的字符：则跳过模式中的"x*"（即j+2），继续匹配 match(i, j+2)
        b. 匹配1个或多个前面的字符：在第一个字符匹配的前提下，匹配s的下一个字符，模式保持不变（因为*可以匹配多个），即 match(i+1, j)
• 否则，如果没有’*'，那么当前字符必须匹配，然后递归匹配剩下的部分：match(i+1, j+1)
        但是注意：递归可能会出现重复子问题，所以效率可能不高，但作为解决方案之一。

public class RegularExpMatch {// 使用Map存储已计算的结果，避免重复计算private Map<String, Boolean> memo = new HashMap<>();public boolean isMatch(String s, String p) {return dp(0, 0, s, p);}private boolean dp(int i, int j, String s, String p) {// 生成唯一键值对，用于记忆化存储String key = i + "," + j;if (memo.containsKey(key)) {return memo.get(key);}// 模式串已用完if (j == p.length()) {return i == s.length();}// 检查当前字符是否匹配boolean firstMatch = (i < s.length()) &&(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');boolean result;// 处理'*'的情况（需要确保j+1不越界）if (j + 1 < p.length() && p.charAt(j + 1) == '*') {// 两种情况：//1. 匹配0个字符（跳过当前字符和*）即匹配0次,不消耗任何字符串字符//2. 匹配1个或多个字符（继续匹配）result = dp(i, j + 2, s, p) || (firstMatch && dp(i + 1, j, s, p));} else {// 没有'*'，正常匹配下一个字符result = firstMatch && dp(i + 1, j + 1, s, p);}// 存储计算结果   memo.put(key, result);return result;}
}

方法二：动态规划

• 初始化：空字符串匹配空模式
• 处理模式开头可能的"x*"匹配空字符串的情况
• 状态转移分三种情况：
  • 普通字符匹配
  • '.'匹配任意字符
  • '*'的两种处理方式（匹配0次或多次）

public boolean isMatch(String s, String p) {int m = s.length(), n = p.length();// dp[i][j]表示s的前i个字符和p的前j个字符是否匹配boolean[][] dp = new boolean[m + 1][n + 1];// 空字符串匹配空模式dp[0][0] = true;// 处理模式开头可能有 "a*" 或 ".*" 的情况（匹配空字符串）for (int j = 2; j <= n; j++) {if (p.charAt(j - 1) == '*') {dp[0][j] = dp[0][j - 2]; // 跳过 "x*" 模式}}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {char sc = s.charAt(i - 1);char pc = p.charAt(j - 1);// 当前字符匹配if (sc == pc || pc == '.') {//如果当前字符匹配，此时的值为去掉当前字符后是否匹配的值dp[i][j] = dp[i - 1][j - 1];}// 处理 '*' 的情况else if (pc == '*') {char prev = p.charAt(j - 2); // '*' 前面的字符，注意i和j表示的是dp表的下标，不是字符串下标，字符值下标还需要-1// 1. 匹配0个字符（跳过 "x*" 模式）dp[i][j] = dp[i][j - 2];// 2. 匹配1个或多个字符（如果前一个字符匹配）if (prev == '.' || prev == sc) {dp[i][j] = dp[i][j] || dp[i - 1][j]; //表示如果匹配0个字符成立就直接返回true了，否则再匹配1个或多个字符}}}}return dp[m][n];
}

考虑字符串 s = “abcde” 和模式 p = “abcc*d*.*de”，我们使用动态规划来解决匹配问题。动态规划表如下：
dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。

总结：匹配0真的难绷，匹配0个我以为只是’*‘没了但其前面的元素还在，结果是’*'和前面一个元素都没了！！！！