05 动态规划字符串匹配：正则表达式与通配符

动态规划字符串匹配：正则表达式与通配符

摘要

本篇深入字符串动态规划的最难范式：LeetCode 10（Regular Expression Matching）和 LeetCode 44（Wildcard Matching）。两道题都被标为困难，核心都是二维 DP，但通配符语义的细微差异（.* vs ?*）导致状态转移方程的处理方式截然不同。彻底理解这两道题，不只是学会写出 dp[i][j] 数组，更重要的是掌握”从左到右逐字符匹配”的思维方式，以及如何将”匹配到目前为止的状态”精确编码成 DP 状态。

---

第 1 章 字符串匹配 DP 的通用框架

1.1 二维 DP 的含义

字符串匹配类 DP 通常定义：

$\text{dp}[i][j]=\text{模式串前 }i\text{ 个字符能否匹配文本串前 }j\text{ 个字符}$

两个字符串各取一个前缀，问这两个前缀是否能匹配——这是”从两个维度同时缩减问题规模”的经典 DP 思路。

下标约定（0 表示空前缀）：

• dp[0][0] = true：空模式匹配空文本
• dp[i][0]：模式前 i 个字符匹配空文本
• dp[0][j]：空模式匹配文本前 j 个字符（通常是 false，除非模式有”可匹配空”的部分）

文本下标：text.charAt(j-1) 是文本的第 j 个字符（1-indexed 的 DP 用 j-1 访问 0-indexed 字符串）。

---

第 2 章 LeetCode 10：正则表达式匹配

2.1 题目

LeetCode 10 - Regular Expression Matching（困难）

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

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

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

输入: s = "aa",   p = "a"   → false（"a" 无法匹配 "aa"）
输入: s = "aa",   p = "a*"  → true（"a*" 可以匹配 0 或多个 a）
输入: s = "ab",   p = ".*"  → true（".*" 匹配任意字符串）
输入: s = "aab",  p = "c*a*b" → true（c* 匹配 0 个 c，a* 匹配 2 个 a，b 匹配 b）

2.2 关键难点：* 的语义

这道题最难的地方不是 DP 本身，而是正确理解 * 的语义：

* 不是独立的元素，它总是与前面的字符组成一个”单元”（如 a*、.*）。这个单元可以匹配 0 个或多个 该字符。

因此，a* 是一个原子单元：

• 匹配 0 个 a（删除这个单元，不消耗文本字符）
• 匹配 1 个 a（消耗文本的 1 个 a，单元继续可用）
• 匹配 2 个 a（消耗文本的 2 个 a，单元继续可用）
• …

2.3 状态转移方程

设 dp[i][j] = p[0..i-1] 能否匹配 s[0..j-1]。

对模式的第 i 个字符 p.charAt(i-1)：

情况 1：p.charAt(i-1) != '*'（普通字符或 .）

直接比较：

$\text{dp}[i][j]=\text{dp}[i-1][j-1]\text{ 且 }(\text{p}[i-1]==\text{s}[j-1]\text{ 或 p}[i-1]==\text{’.’})$

含义：模式前 i-1 个匹配文本前 j-1 个，且第 i 个字符能匹配文本第 j 个字符。

情况 2：p.charAt(i-1) == '*'

* 总是与 p.charAt(i-2)（前一个字符）组成单元，有两种选择：

• 选择 A：* 匹配 0 次（丢弃 p[i-2]* 这个单元）： $\text{dp}[i][j]=\text{dp}[i-2][j]$

• 选择 B：* 匹配 1 次或更多次（消耗文本的一个字符，单元继续）： $\text{dp}[i][j]=\text{dp}[i][j-1]\text{ 且 }(\text{p}[i-2]==\text{s}[j-1]\text{ 或 p}[i-2]==\text{’.’})$ 注意这里用 dp[i][j-1] 而不是 dp[i-2][j-1]，因为 * 单元还没”用完”，可以继续匹配下一个字符。

两种选择满足一种即可：

$\text{dp}[i][j]=\text{dp}[i-2][j]\text{ 或 }(\text{dp}[i][j-1]\text{ 且 match}(i-2,j-1))$

其中 match(i-2, j-1) 表示 p.charAt(i-2) == '.' || p.charAt(i-2) == s.charAt(j-1)。

2.4 初始化

dp[0][0] = true（空模式匹配空文本）
dp[i][0]：当模式第 i 个字符是 '*' 时，dp[i][0] = dp[i-2][0]（用 * 匹配 0 次）
dp[0][j] = false（j > 0，空模式无法匹配非空文本）

2.5 代码实现

public boolean isMatch(String s, String p) {
    int m = p.length(), n = s.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    
    dp[0][0] = true;
    
    // 初始化 dp[i][0]：模式匹配空文本
    // 只有 x* 这样的组合才能匹配空文本（通过 * 匹配 0 次）
    for (int i = 2; i <= m; i++) {
        if (p.charAt(i - 1) == '*') {
            dp[i][0] = dp[i - 2][0];
        }
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(i - 1);
            char sc = s.charAt(j - 1);
            
            if (pc == '*') {
                // 情况 A：* 匹配 0 次（丢弃 p[i-2]* 单元）
                dp[i][j] = dp[i - 2][j];
                
                // 情况 B：* 匹配 1+ 次
                // 需要 p[i-2] 能匹配 s[j-1]
                char prev = p.charAt(i - 2);
                if (prev == '.' || prev == sc) {
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
                }
            } else {
                // 普通字符或 '.'
                if (pc == '.' || pc == sc) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
    }
    
    return dp[m][n];
}

手动验证（s = "aab", p = "c*a*b"）：

p = "c*a*b"（m=5），s = "aab"（n=3）

初始化 dp[0][0]=true
dp[2][0]: p[1]='*', dp[2][0]=dp[0][0]=true（c* 匹配 0 次）
dp[4][0]: p[3]='*', dp[4][0]=dp[2][0]=true（a* 匹配 0 次）

dp[1][1]: pc='c', sc='a', 'c'!='a', dp[1][1]=false
dp[2][1]: pc='*', prev='c'
  A: dp[0][1]=false
  B: 'c'!='a', 不适用
  dp[2][1]=false

dp[3][1]: pc='a', sc='a', match: dp[2][0]=true → dp[3][1]=true
dp[4][1]: pc='*', prev='a'
  A: dp[2][1]=false
  B: 'a'=='a', dp[4][0]=true → dp[4][1]=true

dp[3][2]: pc='a', sc='a', dp[2][1]=false → dp[3][2]=false
dp[4][2]: pc='*', prev='a'
  A: dp[2][2]=?... 
  
（继续完整推导较繁琐，关键路径验证代码正确性建议直接运行）
最终 dp[5][3] = true ✓

复杂度：时间 $O(mn)$，空间 $O(mn)$。

---

第 3 章 LeetCode 44：通配符匹配

3.1 题目

LeetCode 44 - Wildcard Matching（困难）

给你一个输入字符串 s 和一个字符模式 p，请你实现一个支持 ? 和 * 匹配的通配符匹配：

• ? 可以匹配任何单个字符
• * 可以匹配任意字符串（包括空字符串）

匹配需涵盖整个输入字符串（而不是部分）。

输入: s = "aa", p = "*"    → true（* 匹配整个字符串）
输入: s = "cb", p = "?a"   → false（? 匹配 c，但 a 不匹配 b）
输入: s = "adceb", p = "*a*b" → true（第一个 * 匹配空，第二个 * 匹配 "dce"）

3.2 与正则的关键区别

特性	正则（LeetCode 10）	通配符（LeetCode 44）
* 含义	匹配前一个字符 0 次或多次	匹配任意字符串（包括空串）
? 含义	不支持	匹配任意单个字符
. 含义	匹配任意单个字符	不支持
* 是独立元素	否（需要配合前一个字符）	是（* 本身就是元素）

通配符的 * 比正则的 .* 更强大（不需要”前一个字符”约束），但也因此状态转移方程略有不同。

3.3 状态转移方程

设 dp[i][j] = p[0..i-1] 能否匹配 s[0..j-1]。

对模式第 i 个字符 p.charAt(i-1)：

情况 1：p.charAt(i-1) == '*'

* 可以匹配空串或任意字符串，有两种选择：

• 匹配空串：dp[i][j] = dp[i-1][j]（丢弃这个 *）
• 匹配一个字符（消耗文本一个字符，* 继续可用）：dp[i][j] = dp[i][j-1]

$\text{dp}[i][j]=\text{dp}[i-1][j]\text{ 或 dp}[i][j-1]$

情况 2：p.charAt(i-1) == '?' 或 p.charAt(i-1) == sc

普通匹配：

$\text{dp}[i][j]=\text{dp}[i-1][j-1]$

情况 3：其他（字符不匹配）

$\text{dp}[i][j]=\text{false}$

3.4 初始化

dp[0][0] = true
dp[i][0]：只有全是 '*' 的模式才能匹配空文本
           dp[i][0] = dp[i-1][0] && p.charAt(i-1) == '*'
dp[0][j] = false（j > 0）

3.5 代码实现

public boolean isMatch(String s, String p) {
    int m = p.length(), n = s.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    
    dp[0][0] = true;
    
    // 初始化：全是 * 的模式可以匹配空文本
    for (int i = 1; i <= m; i++) {
        dp[i][0] = dp[i - 1][0] && p.charAt(i - 1) == '*';
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(i - 1);
            char sc = s.charAt(j - 1);
            
            if (pc == '*') {
                // * 匹配空（dp[i-1][j]）或匹配一个字符（dp[i][j-1]）
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if (pc == '?' || pc == sc) {
                // ? 或字符匹配
                dp[i][j] = dp[i - 1][j - 1];
            }
            // else: dp[i][j] 保持 false
        }
    }
    
    return dp[m][n];
}

手动验证（s = "adceb", p = "*a*b"）：

p = "*a*b"（m=4）, s = "adceb"（n=5）

dp[0][0]=true
dp[1][0]=true（p[0]='*', dp[0][0]=true）
dp[2][0]=false（p[1]='a'≠'*'）
dp[3][0]=false（dp[2][0]=false）
dp[4][0]=false

dp[1][j]（pc='*'）:
  dp[1][1]: dp[0][1]||dp[1][0] = false||true = true
  dp[1][2]: dp[0][2]||dp[1][1] = false||true = true
  ... dp[1][j] = true for all j

dp[2][1]（pc='a', sc='a'）: dp[1][0]=true → dp[2][1]=true
dp[2][2]（pc='a', sc='d'）: 不匹配, false
dp[2][3]（pc='a', sc='c'）: 不匹配, false
dp[2][4]（pc='a', sc='e'）: 不匹配, false
dp[2][5]（pc='a', sc='b'）: 不匹配, false

dp[3][j]（pc='*'）:
  dp[3][1]: dp[2][1]||dp[3][0] = true||false = true
  dp[3][2]: dp[2][2]||dp[3][1] = false||true = true
  ... dp[3][j] = true for j>=1

dp[4][5]（pc='b', sc='b'）: dp[3][4]=true → dp[4][5]=true ✓

复杂度：时间 $O(mn)$，空间 $O(mn)$，可优化到 $O(n)$（滚动数组）。

---

第 4 章 两道题的对比与深度理解

4.1 核心区别归纳

正则（LeetCode 10）中的 a*：

• a* 是一个”绑定对”，* 的能力取决于前面的字符 a
• 匹配 0 次：dp[i][j] = dp[i-2][j]（跳过整个 a*）
• 匹配 1+ 次：dp[i][j] = dp[i][j-1] && match(p[i-2], s[j-1])（消耗一个字符，a* 单元留用）

通配符（LeetCode 44）中的 *：

• * 是独立元素，能匹配任意字符串
• 匹配空串：dp[i][j] = dp[i-1][j]（丢弃 *）
• 匹配一个字符：dp[i][j] = dp[i][j-1]（* 留用，无需检查字符类型）

直观对比：通配符 * 相当于正则 .*，但无需”前一个字符”约束，所以转移更简单；正则 a* 的转移要同时检查 p[i-2] 能否匹配当前文本字符，更复杂。

4.2 贪心解法（通配符匹配的另一种视角）

通配符匹配还有一个贪心解法，理解起来更直观，但正确性更难证明：

public boolean isMatch(String s, String p) {
    int si = 0, pi = 0;
    int starIdx = -1, sMatch = 0; // 记录上一次 * 的位置和对应的 s 下标
    
    while (si < s.length()) {
        if (pi < p.length() && (p.charAt(pi) == '?' || p.charAt(pi) == s.charAt(si))) {
            si++;
            pi++;
        } else if (pi < p.length() && p.charAt(pi) == '*') {
            starIdx = pi;  // 记录 * 的位置
            sMatch = si;   // 记录此时 s 的位置（* 先匹配空）
            pi++;
        } else if (starIdx != -1) {
            // 回退：让上一个 * 多匹配一个字符
            pi = starIdx + 1;
            sMatch++;
            si = sMatch;
        } else {
            return false;
        }
    }
    
    // 检查剩余模式字符是否全是 *
    while (pi < p.length() && p.charAt(pi) == '*') pi++;
    return pi == p.length();
}

复杂度：时间 $O(mn)$（最坏），空间 $O(1)$。虽然看起来是线性的，但最坏情况下（如 s = "aaab", p = "*ab"）会有回退，实际是 $O(mn)$。

---

第 5 章 面试应对建议

5.1 做字符串 DP 题的通用步骤

1. 定义状态：dp[i][j] 是什么含义（通常是两个字符串各取前缀）
2. 明确初始值：空前缀的边界条件（dp[0][0]、dp[i][0]、dp[0][j]）
3. 推导转移方程：对当前字符的每种情况（普通字符、通配符）分类讨论
4. 确定遍历顺序：外层枚举模式串，内层枚举文本串（或相反，确保依赖的子问题已计算）
5. 返回 dp[m][n]

5.2 容易混淆的地方

下标偏移：dp[i][j] 对应 p[0..i-1] 和 s[0..j-1]，访问字符时用 p.charAt(i-1) 和 s.charAt(j-1)，初学者容易混淆 0-indexed 和 1-indexed。

正则中 * 的判断时机：看到 * 时，要操作的是 p[i-2]（* 前的字符），而不是 p[i-1]（* 本身）。

通配符初始化：dp[i][0] 取决于 dp[i-1][0] && p[i-1]=='*'，需要逐个判断，不能一次性全填 true。

---

下一篇预告

06 字符串整理：最长公共前缀、异位词与计数说 将进入相对轻松的解析类题目。最长公共前缀（LeetCode 14）考察多字符串的纵向扫描；字母异位词分组（LeetCode 49）考察哈希表的分组设计；Count and Say（LeetCode 38）是一道递推生成题，考察”如何读懂一个序列并生成下一个”的模拟能力。三道题类型不同，但都考察字符串的基本操作技能，是面试前的”热身”题。