CS-Notes 剑指 Offer 19：正则表达式匹配——用动态规划实现 `.` 与 `*` 匹配

本篇基于 notes/19. 正则表达式匹配.md 展开，讲解《剑指 Offer》第 19 题“正则表达式匹配”的完整动态规划解法：如何为 .（任意字符）与 *（前导字符重复 0 次或多次）定义状态、推导状态转移方程、处理首行边界初始化，并逐行读懂仓库中的 Java 参考实现。读完后你可以独立写出这道题的 O(mn) 解法，并理解每一行转移对应的匹配语义。

一、题目描述与匹配语义

实现一个函数，用来匹配包括 . 和 * 的正则表达式，规则如下：

• 模式中的字符 . 表示任意一个字符；
• * 表示它前面的字符可以出现任意次（包含 0 次）。

“匹配”是指字符串的所有字符匹配整个模式（full match，而非搜索子串）。题目给出的判定示例：

字符串	模式	是否匹配
aaa	a.a	匹配
aaa	ab*ac*a	匹配
aaa	aa.a	不匹配
aaa	ab*a	不匹配

这里要先厘清元字符语义，仓库中 notes/正则表达式.md 对正则语法有系统梳理，其中与本題直接相关的两点：

• . 是元字符，匹配任何单个字符（绝大多数实现中不匹配换行符），若需匹配字面量的 . 需转义；
• * 是重复匹配元字符，表示前面元素匹配 0 个或多个。

注意本题的 * 语义是“前导字符重复任意次”，这与完整正则引擎中 * 只作用于紧邻的前一个元素的行为一致，但与 {m,n}、+ 等其他量词无关——本题只需处理 . 和 * 两种元字符。

二、解题思路：先避开一个常见误区

原文明确提示了一个关键认知点（见 notes/19. 正则表达式匹配.md 解题思路一节）：

应该注意到，. 是用来当做一个任意字符，而 * 是用来重复前面的字符。这两个的作用不同，不能把 . 的作用和 * 进行类比，从而把它当成重复前面字符一次。

也就是说 * 与 . 没有任何组合关系：a* 是“a 重复 0 次或多次”，不存在 .* 之外的隐式规则。想清楚这一点后，问题就可以抽象成标准的双序列动态规划：给定字符串 str（长度 m）与模式 pattern（长度 n），判断 str 的前 i 个字符能否被 pattern 的前 j 个字符完整匹配。

三、状态定义与状态转移

设 dp[i][j] 表示：字符串的前 i 个字符与模式的前 j 个字符是否匹配。数组规模为 (m+1) x (n+1)，dp[m][n] 即为答案。

逐字符比较时按模式第 j 个字符（下标 j-1）分两类：

情况 1：pattern[j-1] 不是 *

只有当它与 str[i-1] 相等、或它是 . 时，才能各消耗一个字符：

if (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')
    dp[i][j] = dp[i - 1][j - 1];

情况 2：pattern[j-1] 是 *

此时需考察 * 前面的字符 pattern[j-2] 与当前字符 str[i-1] 是否“相等”（相等或为 .）。相等时 * 有三种解释，对应三条转移：

dp[i][j] |= dp[i][j - 1];   // a* counts as single a：x* 消耗 1 个 x
dp[i][j] |= dp[i - 1][j];   // a* counts as multiple a：x* 消耗多个 x
dp[i][j] |= dp[i][j - 2];   // a* counts as empty：x* 整体不出现

不等时，x* 只能整体不出现（出现 0 次），转移退化为：

dp[i][j] = dp[i][j - 2];    // a* only counts as empty

这三条转移覆盖了 * 的全部语义：dp[i][j-1] 对应“重复恰好到当前字符为止”（可重复推导出 1 次的情形），dp[i-1][j] 对应“已重复多次，再来一个”，dp[i][j-2] 对应“重复 0 次、跳过 x* 两个模式字符”。

四、完整 Java 实现与逐行解读

仓库给出的完整实现如下（摘自 notes/19. 正则表达式匹配.md，可直接复制运行）：

public boolean match(String str, String pattern) {

    int m = str.length(), n = pattern.length();
    boolean[][] dp = new boolean[m + 1][n + 1];

    dp[0][0] = true;
    for (int i = 1; i <= n; i++)
        if (pattern.charAt(i - 1) == '*')
            dp[0][i] = dp[0][i - 2];

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')
                dp[i][j] = dp[i - 1][j - 1];
            else if (pattern.charAt(j - 1) == '*')
                if (pattern.charAt(j - 2) == str.charAt(i - 1) || pattern.charAt(j - 2) == '.') {
                    dp[i][j] |= dp[i][j - 1]; // a* counts as single a
                    dp[i][j] |= dp[i - 1][j]; // a* counts as multiple a
                    dp[i][j] |= dp[i][j - 2]; // a* counts as empty
                } else
                    dp[i][j] = dp[i][j - 2];   // a* only counts as empty

    return dp[m][n];
}

逐段说明：

1. dp[0][0] = true：空字符串与空模式匹配，是整个递推的根。
2. 首行初始化（字符串为空、模式非空）：只有形如 a* 的连续模式才可能匹配空串。pattern.charAt(i-1) == '*' 时执行 dp[0][i] = dp[0][i-2]，即“x* 不出现”地向前递推；遇到非 * 字符则保持 false。这保证了例如模式 a*b*c* 能正确判定与空串的匹配。注意该写法依赖 * 前面必有字符，与题目“* 表示它前面的字符”的约定一致。
3. 主循环：按上文两种情况填表，时间复杂度 O(mn)，空间复杂度 O(mn)——由代码中 (m+1) x (n+1) 的二维布尔表可直接确认；由于 dp[i][j] 只依赖上一行与同行左侧状态，空间可压缩到 O(n)，但这属于进一步优化，原实现优先保证可读性。
4. |= 的使用：三条转移取“或”，只要任一种解释成立即匹配成功，这正是 * 多义性的体现。

五、例子走查

以题目示例 str = "aaa", pattern = "ab*ac*a" 走一遍关键格子的推导，验证转移正确性：

• dp[0][3]：模式前 3 位是 ab*，b* 可取 0 次，故 dp[0][3] = dp[0][1] 为 true（空前缀 a 无法匹配空串，但递推链条 dp[0][3]=dp[0][1] 为 false，此处真正起作用的是下面带字符的格子）。
• 匹配第 1 个 a：dp[1][1] = dp[0][0] = true（直接字符相等）。
• 处理 b*：对 b*，b 与当前字符 a 不等，走 dp[i][j] = dp[i][j-2]，即 b* 取 0 次，状态平移到跳过 b*。
• 处理 c* 同理取 0 次；末尾 a 与最后一个 a 相等，dp[3][7] = dp[2][6]，最终 dp[3][7] = true，匹配成功。

而 pattern = "ab*a" 匹配 aaa 失败的原因也能从表格中看出：b* 取 0 次后，模式只剩一个 a 去匹配字符串末尾，中间多出的字符无处消耗，dp[3][4] 最终为 false。

另外注意首行初始化中的一个隐含约束：若模式以 * 开头（如 *a），上面的 dp[0][i] = dp[0][i-2] 会访问下标 -1。本题约定 * 前面必有字符，输入模式合法，因此参考实现未做防御性检查；若用于更通用的输入，需要自行约定这类模式的语义。

六、适用前提与边界约定

• 本题的“匹配”是全串匹配，与 String.matches 语义一致，不同于正则搜索（search）只要求部分匹配；
• 元字符仅两种：. 与 *，不涉及 +、?、[]、分组等语法，后者的系统讲解可参考 notes/正则表达式.md 中“重复匹配”“匹配一组字符”等小节；
• 实现假设模式合法（* 前有字符），且字符比较按 Java char 精确相等判断；
• 该题在仓库的 剑指 Offer 题解 - 目录 中归入“其它”分类，但它本质是字符串双序列 DP，与同目录下 10.1 斐波那契数列 等动态规划题目共享“状态定义 + 转移方程”的解题框架，可与 42. 连续子数组的最大和、48. 最长不含重复字符的子字符串 对照练习 DP 的建模思路。

七、小结

• 状态定义：dp[i][j] = str 前 i 字符能否被 pattern 前 j 字符匹配；
• 非 * 字符：逐字符比对，. 等价于“任意字符”；
• * 字符：前导字符能匹配当前字符时走三条转移（1 次 / 多次 / 0 次），否则只能整体跳过（0 次）；
• 首行按 dp[0][i] = dp[0][i-2] 初始化，覆盖“x* 全取 0 次”的合法空匹配；
• 时间 O(mn)、空间 O(mn)，代码完整可复制自 notes/19. 正则表达式匹配.md。