LeetCode 剑指 Offer 19. 正则表达式匹配
题目描述
题意分析
判断模式
p能否匹配字符串s的全部字符。.匹配任意一个字符，*让它前面的字符或.重复零次或多次。匹配成功时，字符串和模式都必须用完，不能只找到一段局部匹配。
解法：二维动态规划
核心思路
[!blue]
星号可能重复不同次数，直接选择一种次数可能错过答案。用
dp[i][j]保存s的前 $i$ 个字符与p的前 $j$ 个字符是否完整匹配，就能合并这些选择并复用较短前缀的结果。这里的 $i$、$j$ 是长度，最后一个字符的下标分别为i - 1、j - 1。如果
p[j - 1]不是星号，它必须消费字符串的一个字符。只有 $i>0$，且两字符相等或模式字符为.时，才有dp[i][j] = dp[i - 1][j - 1]；字符对不上时，这个状态就是假。如果末尾是星号，就把
p[j - 2]和*当成一组。使用零次时，直接删去这一组，继承dp[i][j - 2]。使用至少一次时，先要求s[i - 1]能匹配p[j - 2]，再用这一组消费当前字符，继承dp[i - 1][j]。模式长度保持不变，才能继续消费更多字符，也能在后续状态选择零次结束重复；两种情况只要有一种成立即可。初始只有
dp[0][0] = true：空模式不能匹配非空串，因此dp[i][0]在 $i>0$ 时为假。空串这一行也要参与计算，普通字符无法匹配它，星号组则可以通过零次分支不断向左退两格，从而判断整个模式是否都能省略。转移只依赖当前行左侧的
dp[i][j - 2]，以及上一行的状态。所以按 $i$ 从 0 到 $m$、$j$ 从 1 到 $n$ 递增计算，依赖都已就绪，最终dp[m][n]就表示完整匹配结果。
解题步骤
- 设字符串、模式长度分别为 $m$、$n$，建立大小为 $(m+1)\times(n+1)$ 的布尔表。
- 将
dp[0][0]设为真，其余状态初始为假。- 按上述顺序遍历所有前缀；普通字符或
.检查匹配后继承左上状态。- 遇到
*时，合并零次使用与消费一个字符后继续使用的两条分支。- 返回
dp[m][n]。
代码实现
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++) {
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]
}
复杂度分析
- 时间复杂度：$O((m+1)(n+1))$，包含空串状态。
- 空间复杂度：$O((m+1)(n+1))$，二维布尔表。
关键点总结
[!green]
- 星号零次退模式两格，重复只退字符串一格。
- 读取当前字符前先保证字符串前缀非空。
- 零次和重复分支可能同时成立，用逻辑或合并即可，不需要提前决定重复次数。
易错点总结
[!yellow]
- 将重复分支模式也退两格，会限制星号只能使用一次。
- 漏掉空串行，无法匹配零次组合。
- 把一次局部匹配当完整成功，未确认两串都被覆盖。
*不能独立匹配任意串；它只能重复前一个元素。题目保证星号前有有效元素，因此星号分支访问j - 2是安全的。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 44. 通配符匹配 | 困难 | 两题都是模式匹配，但正则星号重复前一个元素，通配符星号独立匹配任意串，转移不能混用。 |
| 115. 不同的子序列 | 困难 | 同样按文本与模式的前缀建立二维状态，原题计数匹配子序列，本题判断完整正则匹配。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！