正则表达式匹配——DP与NFA的等价性分析

老张2026/4/30大约 8 分钟

正则表达式匹配——DP与NFA的等价性分析

适读人群：Java后端工程师、Hard题挑战者 | 阅读时长：约25分钟 | 难度：Hard

开篇故事

正则表达式匹配是LeetCode第10题，也是我认为DP题目里逻辑最复杂的之一。

这道题的难点不在于代码量，而在于 * 这个通配符的处理逻辑。* 代表"前一个字符出现0次或多次"，这个"0次"是关键——当你决定 * 匹配0次时，整个模式会向前跳跃，这种"可以跳过"的行为，用递归描述直觉，用DP实现却要格外小心。

我在一次面试中见过这道题，面试官让我现场推导状态转移方程，不让背答案。当时推了大概十分钟，把所有情况一一列举，才得出完整的转移方程。

更有意思的是，正则匹配的DP，本质上等价于NFA（非确定有限自动机）的模拟执行。理解了这个等价性，你对这道题的理解就上升了一个层次——它不只是一道算法题，它是理论计算机科学在算法竞赛里的一次具体体现。

一、题目解析

题号：LeetCode 10. Regular Expression Matching

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

. 匹配任意单个字符
* 匹配零个或多个前面的那一个元素

注意：匹配应该覆盖整个字符串 s，而不是部分字符串。

示例：

输入：s = "aa"，p = "a*"，输出：true（a* 匹配两个 a）
输入：s = "ab"，p = "."，输出：true（. 匹配任意序列）
输入：s = "aab"，p = "cab"，输出：true（c* 匹配0个c，a* 匹配2个a，b匹配b）

数据范围：1 ≤ s.length ≤ 20，1 ≤ p.length ≤ 30，p 中每个 * 前面都有一个合法的字符

二、DP思路推导

2.1 状态定义

定义 dp[i][j] = s 的前 i 个字符能否被 p 的前 j 个字符完全匹配

dp[i][j] = true：s[0..i-1] 与 p[0..j-1] 匹配
dp[i][j] = false：不匹配

使用1-indexed，避免字符串索引偏移问题。

2.2 状态转移方程（分情况讨论）

情况一：p[j-1] 是普通字母或 .

当前模式字符不是 *，那么必须直接匹配 s[i-1]：

dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.')

含义：前 i-1 个字符和前 j-1 个模式匹配，且当前字符也匹配。

情况二：p[j-1] 是 *

* 的语义是"前一个字符出现0次或多次"，所以 * 总是与前面的字符成对出现。设 * 前面的字符是 c = p[j-2]。

分两种情况：

子情况A：* 匹配0次（跳过 c* 这两个字符）

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

直接忽略模式里的 c*，等价于模式跳过这两个字符。

子情况B：* 匹配1次或多次（s[i-1] 与 c 匹配）

前提：s[i-1] 与 c 匹配（s[i-1] == c 或 c == '.'）

此时 c* 消耗了 s[i-1] 一个字符，但 c* 还可以继续匹配更多：

dp[i][j] = dp[i-1][j]  （c* 消耗一个s字符，但模式不动）

完整的 * 情况：

if p[j-1] == '*':
    dp[i][j] = dp[i][j-2]   // c* 匹配0次
    if s[i-1] == p[j-2] or p[j-2] == '.':
        dp[i][j] = dp[i][j] || dp[i-1][j]  // c* 消耗s的一个字符

理解 dp[i-1][j]：当 c* 匹配了 s[i-1] 这一个字符后，剩下的任务是：s 的前 i-1 个字符仍然需要被 p 的前 j 个字符匹配（因为 c* 还可以继续匹配，模式不向前移动）。

2.3 边界条件

dp[0][0] = true：空串和空模式，匹配
dp[i][0] = false（i > 0）：非空串和空模式，不匹配
dp[0][j]：空串与模式的匹配，只有当模式是 a*b*c* 这种形式（每个字符后跟 *）时才为 true

空串的边界处理：

dp[0][0] = true;
// 处理p开头连续的x*y*z*能匹配空串的情况
for (int j = 2; j <= pLen; j += 2) {
    dp[0][j] = dp[0][j-2] && p.charAt(j-1) == '*';
}

2.4 状态转移示意

s = "aab", p = "c*a*b"

     ""  c  *  a  *  b
""  [T   F  T  F  T  F]   ← 空串匹配：c*可以0次，a*可以0次，b不能为0次
 a  [F   F  F  T  T  F]
 a  [F   F  F  F  T  F]
 b  [F   F  F  F  F  T]   ← dp[3][5] = true ✓

三、解法一：基础二维DP

public class RegularExpressionMatching {
    
    /**
     * 10. 正则表达式匹配 - 二维DP
     * 时间复杂度：O(m * n)，m=s.length, n=p.length
     * 空间复杂度：O(m * n)
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        
        // dp[i][j] = s前i个字符与p前j个字符是否完全匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        
        // 边界1：空串和空模式匹配
        dp[0][0] = true;
        
        // 边界2：空串与模式的匹配（只有x*y*z*能匹配空串）
        for (int j = 2; j <= n; j++) {
            // p[j-1]为'*'，且前面的状态也能匹配空串
            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);  // 当前模式字符
                char sc = s.charAt(i - 1);  // 当前文本字符
                
                if (pc == '*') {
                    // c* 匹配0次：忽略 c* 这两个模式字符
                    dp[i][j] = dp[i][j - 2];
                    
                    // c* 匹配1次或多次（前提：当前文本字符与c匹配）
                    char prevPc = p.charAt(j - 2);  // * 前面的字符c
                    if (prevPc == '.' || prevPc == sc) {
                        // 消耗s的一个字符，模式不动（c* 还可继续匹配）
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    // 普通字符或'.'：必须直接匹配
                    if (pc == '.' || pc == sc) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    // 否则 dp[i][j] 保持 false（Java 默认）
                }
            }
        }
        
        return dp[m][n];
    }
}

Mermaid状态转移分支图：

四、解法二：记忆化递归（直观版）

/**
 * 10. 正则表达式匹配 - 记忆化递归
 * 递归思路更直觉，逻辑更清晰
 */
public boolean isMatchMemo(String s, String p) {
    Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
    return dfs(s, p, 0, 0, memo);
}

private boolean dfs(String s, String p, int i, int j, Boolean[][] memo) {
    // 模式耗尽
    if (j == p.length()) return i == s.length();
    // 文本耗尽，但模式未耗尽（只有x*y*...能匹配）
    if (memo[i][j] != null) return memo[i][j];
    
    // 当前位置是否匹配（文本未耗尽时）
    boolean firstMatch = i < s.length() && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i));
    
    boolean result;
    if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
        // 下一个模式字符是*
        result = dfs(s, p, i, j + 2, memo)                 // * 匹配0次（跳过c*）
              || (firstMatch && dfs(s, p, i + 1, j, memo)); // * 匹配1+次
    } else {
        // 普通字符或'.'
        result = firstMatch && dfs(s, p, i + 1, j + 1, memo);
    }
    
    memo[i][j] = result;
    return result;
}