LeetCode 剑指 Offer 19. 正则表达式匹配
目录
题目描述
题意分析
给一个只含小写字母的字符串
s和一个模式串p，p里除了小写字母还可能出现两个特殊字符：.匹配任意单个字符，*表示它前面那个字符可以出现零次或多次。要判断p能否匹配s的全部内容，返回布尔值。
「完整匹配」而不是「部分匹配」是第一个要盯住的点：
s = "aa"、p = "a"返回false，因为p只覆盖了前半段。这决定了最终答案取的是「s用完且p用完」这个状态，而不是中途任何一次成功。
*的语义是本题全部难度的来源。它不是一个独立的通配符，而是一个作用在前一个字符上的量词，所以p里的x*必须被当成一个不可分割的单元来处理；同时「零次或多次」意味着同一个x*面对同一个位置会有两种走法——要么整体作废，要么再吃掉s的一个字符后自己留在原地继续待命。一个决策点分出两个分支、分支之间还会重叠，这正是需要动态规划而不是贪心或单趟扫描的信号。
题目保证
*不会出现在p的开头，也不会有连续的两个*，所以看到p[j-1] == '*'时，p[j-2]一定存在且一定是普通字符或.，可以放心访问。
边界要盯住：
s可以为空而p非空，此时只有形如a*b*c*的模式能匹配；p为空时只有s也为空才成立；.不能匹配「没有字符」，它必须消耗一个字符；.*组合可以匹配任意长度的任意内容。
解法：二维动态规划
核心思路
递归匹配在遇到
x*时会分成「不用x*」和「让它再匹配一个字符」两条路；不同路径又会反复到达同一组字符串前缀，因此用动态规划消除重复计算。定义
dp[i][j]：s的前i个字符能否被p的前j个字符完整匹配。字符相等，或模式字符为.，记为当前字符可以匹配。
p[j-1]不是*：它必须消耗一个字符。当前字符可匹配时，dp[i][j] = dp[i-1][j-1]。p[j-1]是*：它与p[j-2]组成x*。要么让x出现零次，转到dp[i][j-2]；要么在x能匹配s[i-1]时再消耗一个字符，转到dp[i-1][j]。后一种情况j不变，因为同一个x*仍可继续使用。初始状态只有
dp[0][0] = true。外层从i = 0开始填表，空串遇到a*b*时会通过dp[0][j-2]自动完成初始化。所有依赖都位于上一行或本行左侧，按行递增即可。正确性来自对模式末尾的完备分类：普通字符只有「两边各消耗一个」这一种可能；
x*匹配成功时，最后一步必然是「使用零次」或「至少使用一次」。两类转移覆盖全部合法匹配且没有引入非法匹配，所以最终dp[m][n]就是答案。
解题步骤
- 创建
(m + 1) × (n + 1)的布尔表，令dp[0][0] = true。- 枚举
i = 0..m、j = 1..n，保证转移所依赖的状态已经计算。- 若
p[j-1]是普通字符或.，仅当i > 0且当前字符可匹配时，继承dp[i-1][j-1]。- 若
p[j-1]是*，先取零次分支dp[i][j-2]；若i > 0且p[j-2]能匹配s[i-1]，再合并多次分支dp[i-1][j]。- 返回
dp[m][n]，只有字符串和模式都用完才算完整匹配。以
s = "aab"、p = "c*a*b"为例：c*和a*都可取零次，因此dp[0][2]、dp[0][4]为真；随后a*通过dp[0][4] → dp[1][4] → dp[2][4]连续匹配两个a；末尾b再由dp[2][4]转到dp[3][5]，得到true。
复杂度分析
- 时间复杂度：$O(mn)$，共计算 $(m+1)(n+1)$ 个状态，每个状态只做常数次判断。
- 空间复杂度：$O(mn)$。虽然可以压缩到 $O(n)$，但二维表更容易解释和避免覆盖依赖，适合作为面试主解法。
关键点总结
- 状态使用前缀长度，才能自然表示空串，并让答案直接落在
dp[m][n]。*与前一个字符组成整体：零次分支退两格，多次分支只让字符串退一格。- 多次分支保留
j，正是x*能重复匹配的原因。- 填表必须包含
i = 0这一行，否则空串无法被a*b*匹配。
易错点总结
- 把多次分支写成
dp[i-1][j-2]：s = "aa"、p = "a*"会错误地限制a*只能使用一次。- 零次分支只退一格：应丢掉完整的
x*，所以是j-2，不是j-1。- 忘记
i > 0：处理空串时访问s[i-1]会越界，.也不能匹配空字符。- 只从
i = 1开始填表：s = ""、p = "a*"会被误判为false。- 对
*使用贪心：s = "aab"、p = "a*ab"需要回退分配，单纯尽量多匹配并不正确。
代码实现
class Solution {
public 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 i = 0; 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]
|| i > 0 && matches(s.charAt(i - 1), p.charAt(j - 2)) && dp[i - 1][j];
} else if (i > 0 && matches(s.charAt(i - 1), pc)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
private boolean matches(char sc, char pc) {
return pc == '.' || sc == pc;
}
}
func isMatch(s string, p string) bool {
m, n := len(s), len(p)
dp := make([][]bool, m+1)
for i := range dp {
dp[i] = make([]bool, n+1)
}
dp[0][0] = true
matches := func(sc, pc byte) bool {
return pc == '.' || sc == pc
}
for i := 0; i <= m; i++ {
for j := 1; j <= n; j++ {
pc := p[j-1]
if pc == '*' {
dp[i][j] = dp[i][j-2] ||
i > 0 && matches(s[i-1], p[j-2]) && dp[i-1][j]
} else if i > 0 && matches(s[i-1], pc) {
dp[i][j] = dp[i-1][j-1]
}
}
}
return dp[m][n]
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 10. 正则表达式匹配 | 困难 | 与本题同题，可直接套用同一张 DP 表 |
| 44. 通配符匹配 | 困难 |
* 独立匹配任意长度，不再绑定前一个字符，转移只需看上方与左方两个格子，还能用贪心双指针做到 $O(1)$ 空间 |
| 72. 编辑距离 | 中等 | 同样是两串前缀的二维 DP，但求最小操作数而非布尔可达，转移取三个方向的最小值 |
| 1143. 最长公共子序列 | 中等 | 二维前缀 DP 的最基础形态，字符相等时对角线加一，否则取上、左较大者 |
| 115. 不同的子序列 | 困难 | 统计匹配方案数而不是判定可行，转移由「或」变成「加」 |
| 97. 交错字符串 | 中等 | 两个源串交错拼成目标串，状态仍是两个前缀长度，但第三个串的位置由二者之和确定 |
| 392. 判断子序列 | 简单 | 没有通配符，贪心双指针一趟即可，是理解「何时不需要 DP」的对照组 |
| 139. 单词拆分 | 中等 | 单串上的可达性 DP，转移要枚举上一个断点而非固定几个方向 |