正则表达式匹配中的 . 和 * 如何用动态规划处理？

简化版

正则匹配用 dp[i][j] 表示 s 的前 i 个字符能否匹配 p 的前 j 个字符。普通字符或 . 匹配时看 dp[i-1][j-1]；遇到 * 时有两种情况：让前一个模式字符出现 0 次，或在当前字符匹配时让它出现多次。

详细版

若 p[j-1] != '*'，则必须当前字符能匹配，并且前缀也匹配：dp[i][j] = match(s[i-1], p[j-1]) && dp[i-1][j-1]。若 p[j-1] == '*'，它修饰的是 p[j-2]，可以出现 0 次：dp[i][j] |= dp[i][j-2]；若 p[j-2] 能匹配 s[i-1]，还可以出现 1 次或多次：dp[i][j] |= dp[i-1][j]。

初始化 dp[0][0]=true，并处理空字符串匹配如 "a*", "a*b*" 的情况。复杂度 O(mn)。

完整版教学

一、先明确题目里的正则语义

这里的模式只包含两种特殊符号：

符号	含义
`.`	匹配任意单个字符
`*`	匹配前一个元素 0 次或多次

例如：

s = "aab"
p = "c*a*b"
c* 出现 0 次
a* 出现 2 次
b  出现 1 次
结果匹配

二、状态定义

定义：

dp[i][j]：s 的前 i 个字符，能否匹配 p 的前 j 个字符

答案是 dp[m][n]。使用“前 i 个字符”可以自然表达空串状态，比如 dp[0][j] 表示空字符串能否被模式前缀匹配。

记忆钩子：双字符串匹配题，先把状态定义成两个前缀是否匹配。

三、普通字符和点号怎么转移

当 p[j-1] 不是 * 时，它必须和 s[i-1] 匹配：

字符相同，或模式字符是 '.'

如果当前字符匹配，答案取决于前面的前缀：

dp[i][j] = dp[i-1][j-1]

如果当前字符不匹配，则 dp[i][j]=false。

四、星号匹配 0 次

当 p[j-1] == '*' 时，它修饰 p[j-2]。如果让 p[j-2]* 整体出现 0 次，相当于删除这两个模式字符：

dp[i][j] = dp[i][j-2]

例如 "aab" 匹配 "c*a*b" 时，c* 可以直接被跳过。

五、星号匹配 1 次或多次

如果 p[j-2] 能匹配当前字符 s[i-1]，那么 * 可以继续消耗一个字符。模式仍停在 j，字符串退一位：

dp[i][j] = dp[i][j] || dp[i-1][j]

这表示 p[j-2]* 已经匹配了当前字符，接下来继续用同一个模式片段匹配更短的字符串前缀。

六、初始化空字符串

dp[0][0]=true，空模式匹配空字符串。对于模式前缀，如果形如 "a*", "a*b*", ".*"，也可能匹配空串。

for j = 2..n:
  if p[j-1] == '*':
      dp[0][j] = dp[0][j-2]

这一步漏掉后，很多空串相关用例会失败。

七、代码模板

boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;

    for (int j = 2; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(j - 1);
            if (pc == '*') {
                dp[i][j] = dp[i][j - 2];
                char prev = p.charAt(j - 2);
                if (prev == '.' || prev == s.charAt(i - 1)) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            } else if (pc == '.' || pc == s.charAt(i - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}

默认题目保证 * 不会作为模式第一个字符；如果业务场景不保证，需要额外校验非法模式。

八、常见误区与追问

误区：把 * 当作匹配任意字符串。 * 只修饰前一个元素，不是独立通配符。
误区：漏掉匹配 0 次。 a* 可以完全不出现，所以要看 dp[i][j-2]。
误区：多次匹配时写成 dp[i-1][j-1]。 多次匹配后模式仍要停在 j，应看 dp[i-1][j]。
追问：为什么要初始化 dp[0][j]？ 空字符串可能被多个 x* 模式匹配。
追问：复杂度是多少？ 状态数 O(mn)，每个状态常数转移。
追问：和通配符匹配有什么区别？ 通配符匹配里 * 通常独立代表任意字符串，本题的 * 修饰前一个字符。

九、加强记忆

正则匹配最容易错在 *。先把状态定成两个前缀是否匹配；普通字符和 . 都走对角线 dp[i-1][j-1]；遇到 * 就分两条路：出现 0 次时删掉前一个字符和星号，看 dp[i][j-2]；出现多次时必须当前字符可匹配，并且模式停在原地，看 dp[i-1][j]。这两个分支讲清楚，比背整段代码更重要。

简化版

详细版