LeetCode 10. 正则表达式匹配
目录
题目描述
题意分析
输入两个串：待匹配的字符串
s（只含小写字母）和模式串p（含小写字母、.和*）。要回答的是一个判定问题：p能否匹配s，返回布尔值。模式的语义要逐条读清楚：
- 普通小写字母只匹配与自己相同的那一个字符。
.匹配任意一个单字符，但必须匹配掉一个，不能匹配空。*本身不是一个独立的模式单元，它依附于紧挨在它前面的那个字符（字母或.），表示「该字符重复出现零次或多次」。因此p中的*一定不会出现在首位，也不会紧跟另一个*，a*、.*这样的两字符组合才是真正的基本单位。- 关键在于「零次」也是合法的：
a*可以什么都不匹配，c*a*能匹配空串。最容易被忽略的一条是：题目要求 完全匹配，即整个
s必须被整个p覆盖，而不是在s中找到某个匹配的子串。所以s = "aa"、p = "a"返回false，尽管p匹配了s的一个前缀。边界上，
s可以为空串，p也可以为空串；两串长度都不超过 20，规模很小，说明可以接受平方级甚至更高的算法。
解法：二维动态规划处理星号转移
核心思路
问题关键：题目要求整个字符串与整个模式完全匹配。普通字符和
.都固定消费一个字符，只有x*会产生“使用零次”或“使用一次以上”的分支；直接回溯会重复计算相同的字符串、模式位置。为什么选二维动态规划：递归子问题只由两个前缀长度决定。定义
dp[i][j]表示s的前i个字符能否与p的前j个字符完全匹配，最终答案是dp[m][n]。根据模式前缀的最后一个单元转移：
- 若
p[j - 1]不是*，它必须与s[i - 1]相容（字符相等或模式字符为.），再看dp[i - 1][j - 1]；- 若
p[j - 1] == '*'，把p[j - 2]与*看成整体。用零次时跳过x*，取dp[i][j - 2]；用一次以上时，当前字符必须与x相容，消费一个字符串字符但保留模式，取dp[i - 1][j]。初始
dp[0][0] = true。循环让i从 0 开始，这样a*、c*a*可通过“用零次”递推出与空串匹配，无需单独初始化首行。正确性：非星号结尾只能一一匹配最后两个字符；星号结尾必然来自
x*使用零次或至少一次，前者跳过x*，后者消费一个字符并保留模式。两种来源可能同时成立，取或即可，并且它们覆盖全部情况。每次转移都去掉至少一个已确定的字符或模式单元，因此按前缀长度归纳，所有dp状态都正确。
解题步骤
- 建立
(m + 1) x (n + 1)的布尔表，设置dp[0][0] = true。- 枚举
i = 0..m、j = 1..n，第 0 行用于处理可匹配空串的连续x*。- 非
*：仅当i > 0且末字符相容时，从dp[i - 1][j - 1]转移。*：先取dp[i][j - 2]表示零次；若i > 0且前导字符相容，再或上dp[i - 1][j]表示继续重复。- 返回
dp[m][n]，不能在中途看到某个真值就提前返回。面试口述示例：
s = "aab", p = "c*a*b"。c*用零次，a*先通过dp[0][4]匹配空串，再连续消费两个a而保持模式列不动，最后b与b一一匹配，所以答案为true。边界反例：空串与
a*匹配；aa与a不完全匹配；ab与.*匹配。三者分别检验星号零次、完全匹配和“任意字符重复”的语义。
代码实现
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int 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++) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2];
if (i > 0 && matches(s, p, i, j - 1)) {
dp[i][j] |= dp[i - 1][j];
}
} else if (i > 0 && matches(s, p, i, j)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
private boolean matches(String s, String p, int i, int j) {
return p.charAt(j - 1) == '.'
|| s.charAt(i - 1) == p.charAt(j - 1);
}
}
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
for i := 0; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
dp[i][j] = dp[i][j-2]
if i > 0 && regexMatches(s, p, i, j-1) {
dp[i][j] = dp[i][j] || dp[i-1][j]
}
} else if i > 0 && regexMatches(s, p, i, j) {
dp[i][j] = dp[i-1][j-1]
}
}
}
return dp[m][n]
}
func regexMatches(s string, p string, i int, j int) bool {
return p[j-1] == '.' || s[i-1] == p[j-1]
}
复杂度分析
- 时间复杂度：$O(mn)$，共有 $(m + 1)(n + 1)$ 个状态，每个状态只做常数次判断。
- 空间复杂度：$O(mn)$，保存完整状态表。转移只依赖当前行和上一行，可压成 $O(n)$，但二维表更适合面试推导和排查边界。
关键点总结
- 状态必须表达“两个前缀完全匹配”，这样
dp[m][n]才直接对应题意。x*是一个模式单元：零次跳两列，多次时字符串退一格、模式列不动。- 题目保证模式合法，因此遇到
*时必有前导元素，访问j - 2不会越界。.只匹配一个字符；.*能匹配任意长度，是.与*两种语义的组合。- 从空字符串这一行开始递推，才能保留
a*、c*a*等模式匹配空串的能力。
易错点总结
- 星号零次写成
dp[i][j - 1]：只丢掉*却留下x，正确转移必须跳过两列。- 星号多次写成
dp[i - 1][j - 2]：模式被提前丢弃，a*无法继续匹配aaa。- 只按前导字符是否匹配在“零次”和“多次”间二选一：
s = "a", p = "aa*"虽然末字符相同，却必须让末尾a*使用零次；应对两个完整状态取或。- 忽略
i > 0就比较字符：空字符串场景会访问s[-1]。- 外层从
i = 1开始：dp[0][2]无法由dp[0][0]推出，空串与a*会被误判。- 把本题当子串匹配：
s = "aa", p = "a"必须为false，答案只能取完整前缀状态dp[m][n]。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 44. 通配符匹配 | 困难 |
* 独立通配任意串，另有贪心 $O(1)$ 空间解 |
| 剑指 Offer 19. 正则表达式匹配 | 困难 | 与本题同题，可用来复习星号双支转移 |
| 72. 编辑距离 | 中等 | 双序列 DP 求最小操作数而非布尔判定 |
| 97. 交错字符串 | 中等 | 双前缀布尔 DP，转移来自两个串各退一格 |
| 115. 不同的子序列 | 困难 | 双序列 DP 统计方案数，含「用与不用」两支 |
| 1143. 最长公共子序列 | 中等 | 双序列 DP 求最优长度的入门模板 |