LeetCode 10. 正则表达式匹配
题目描述
题意分析
给定字符串
s和合法模式p，判断整个字符串能否被整个模式匹配，返回布尔值。普通字母只匹配相同的字母，.匹配任意一个字符，*表示它前面的那个元素可以重复零次、一次或多次。
*依附于前一个元素，本身不能独立表示任意字符串；前一个元素也可以是.。重复零次意味着这一整个模式单元都不消耗字符。匹配必须同时用完文本和模式，只有某段子串匹配并不够。题目保证每个星号都有合法的前导元素，不需要解析其他正则语法。
解法：二维动态规划处理星号转移
核心思路
[!blue]
星号可以选择重复多少次，直接贪心消耗字符可能占用后面模式所需的内容。用动态规划保留所有可能：定义
dp[i][j]为文本前i个字符能否与模式前j个字符完全匹配。这里i、j是前缀长度，对应的末字符下标分别为i - 1、j - 1。若模式末尾不是星号，就必须消耗一个文本字符。仅当
i > 0，且模式末字符等于文本末字符或为.时，才可能匹配；剩下两段前缀是否匹配由dp[i - 1][j - 1]决定。若模式末尾为
x*，把所有合法匹配按这一单元使用次数拆成两类。使用零次时，文本不动、整个x*被跳过，来源是dp[i][j - 2]。使用至少一次时，文本末字符必须能被x匹配；去掉这一次后，前面的文本仍由包含x*的完整模式匹配，来源是dp[i - 1][j]。保留模式列j，才能允许同一个单元继续重复。这两类情况共同覆盖所有匹配，因此取逻辑或。即使末字符与
x相容，也不能强制使用星号：零次方案仍可能是唯一能让此前部分完整匹配的方案。空文本和空模式可以匹配，令
dp[0][0] = true；非空文本不能匹配空模式，第一列其余位置保持false。外层从i = 0开始，让第一行通过星号的零次分支向右传播，从而识别能匹配空文本的模式。按行从上到下、按列从左到右填表，上一行与本行更左的依赖都已完成，最终返回dp[m][n]。
解题步骤
- 建立
(m + 1) × (n + 1)的布尔表，只将dp[0][0]设为真。- 枚举文本前缀长度
i = 0..m，再枚举模式前缀长度j = 1..n。- 模式末尾不是星号时，若文本非空且末字符相容，继承
dp[i - 1][j - 1]。- 模式末尾是星号时，先取
dp[i][j - 2]；若文本非空且末字符与星号前的元素相容，再或上dp[i - 1][j]。- 返回完整前缀的状态
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++) {
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、n分别为文本和模式长度。每个前缀对只计算一次，每次至多检查两个来源。- 空间复杂度：$O(mn)$，保存二维布尔状态表。
关键点总结
[!green]
- 状态必须表示两个前缀完全匹配，不能混成“其中存在匹配片段”。
- 星号零次跳过整个模式单元；至少一次只缩短文本，保留模式继续匹配。
- 第一行负责空文本，第一列负责空模式；字符比较前先保证文本前缀非空。
易错点总结
[!yellow]
- 星号取零次时只退一列，会留下它前面的元素；必须一起跳过两列。
- 星号重复时退到
j - 2，相当于提前丢掉整个重复单元，无法表示继续使用它。- 末字符相容就只考虑重复分支，会漏掉必须让当前星号取零次的匹配方案；两个来源应取或。
- 忽略
i > 0就读取文本末字符，会在处理第一行时访问负下标。- 不处理
i = 0的一行，会丢失模式先匹配空前缀再匹配后续文本的路径。.只消耗一个字符；.*能消耗任意多个字符，来自星号的重复能力，不能混为同一种转移。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 44. 通配符匹配 | 困难 | 两题都是模式匹配，但正则星号重复前一个元素，通配符星号独立匹配任意串，转移不能混用。 |
| 115. 不同的子序列 | 困难 | 同样按文本与模式的前缀建立二维状态，原题计数匹配子序列，本题判断完整正则匹配。 |