LeetCode 10. 正则表达式匹配
题目描述
思路分析
解法一：动态规划（推荐）
核心思路：
dp[i][j]表示s的前i个字符与p的前j个字符是否匹配。- 初始化：
dp[0][0] = true；空串只能被a*b*c*形式的模式匹配，当p[j-1] == '*'时，dp[0][j] = dp[0][j-2]。- 状态转移分两种情况：
p[j-1]为普通字符或.：dp[i][j] = dp[i-1][j-1]，条件是s[i-1] == p[j-1]或p[j-1] == '.'。p[j-1] == '*'：*与前一个字符p[j-2]配对，分两种子情况：
- 用 0 次（消掉
p[j-2]p[j-1]这对）：dp[i][j] |= dp[i][j-2]- 用 1+ 次（
s[i-1]能与p[j-2]匹配时，消掉s[i-1]继续让*匹配剩余）：dp[i][j] |= dp[i-1][j]
复杂度分析：
- 时间复杂度：O(m × n)，其中 m、n 分别为字符串 s 和模式串 p 的长度
- 空间复杂度：O(m × n)，使用二维 DP 表存储所有子问题结果
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;
// 空串与 a*b*c* 形式的模式匹配
for (int j = 2; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
// 用 0 次：消掉 p[j-2]p[j-1] 这一对
dp[i][j] = dp[i][j - 2];
// 用 1+ 次：s[i-1] 能与 p[j-2] 匹配时，消掉 s[i-1] 继续匹配
boolean charMatch = p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.';
if (charMatch) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
// 普通字符或 '.'：首尾对应字符匹配，取左上角状态
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
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
// 空串与 a*b*c* 形式的模式匹配
for j := 2; j <= n; j++ {
if p[j-1] == '*' {
dp[0][j] = dp[0][j-2]
}
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
// 用 0 次：消掉 p[j-2]p[j-1] 这一对
// 用 1+ 次：s[i-1] 能与 p[j-2] 匹配时，消掉 s[i-1] 继续匹配
dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (p[j-2] == s[i-1] || p[j-2] == '.'))
} else if p[j-1] == '.' || p[j-1] == s[i-1] {
// 普通字符或 '.'：首尾对应字符匹配，取左上角状态
dp[i][j] = dp[i-1][j-1]
}
}
}
return dp[m][n]
}
解法二：递归 + 记忆化
核心思路：
- 定义
dp(i, j)表示s[i..]与p[j..]是否匹配，用哈希表缓存已计算结果。- 若
j到达末尾，返回i是否也到达末尾。- 判断当前字符是否匹配：
firstMatch = i < m && (s[i] == p[j] || p[j] == '.')。- 若
p[j+1] == '*'：
- 用 0 次：跳过
p[j]p[j+1]，递归dp(i, j+2)- 用 1+ 次：当前字符匹配时，消耗
s[i]继续，递归dp(i+1, j)- 否则：当前字符匹配时递归
dp(i+1, j+1)，否则返回false。
复杂度分析：
- 时间复杂度：O(m × n)，其中 m、n 分别为 s 和 p 的长度，每个子问题只计算一次
- 空间复杂度：O(m × n)，记忆化缓存及递归调用栈空间
class Solution {
private String s, p;
// 记忆化缓存，-1 表示未计算，0 表示 false，1 表示 true
private int[][] memo;
public boolean isMatch(String s, String p) {
this.s = s;
this.p = p;
memo = new int[s.length() + 1][p.length() + 1];
for (int[] row : memo) {
java.util.Arrays.fill(row, -1);
}
return dp(0, 0);
}
private boolean dp(int i, int j) {
int m = s.length(), n = p.length();
// 模式串用完，看原串是否也用完
if (j == n) {
return i == m;
}
if (memo[i][j] != -1) {
return memo[i][j] == 1;
}
// 当前字符是否匹配
boolean firstMatch = i < m && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
boolean result;
if (j + 1 < n && p.charAt(j + 1) == '*') {
// 用 0 次：跳过 p[j]p[j+1]；用 1+ 次：消耗 s[i] 继续
result = dp(i, j + 2) || (firstMatch && dp(i + 1, j));
} else {
// 普通字符或 '.'：当前匹配则递推
result = firstMatch && dp(i + 1, j + 1);
}
memo[i][j] = result ? 1 : 0;
return result;
}
}
func isMatch(s string, p string) bool {
m, n := len(s), len(p)
// 记忆化缓存，0 表示未计算，1 表示 true，-1 表示 false
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
}
var dp func(i, j int) bool
dp = func(i, j int) bool {
// 模式串用完，看原串是否也用完
if j == n {
return i == m
}
if memo[i][j] != 0 {
return memo[i][j] == 1
}
// 当前字符是否匹配
firstMatch := i < m && (s[i] == p[j] || p[j] == '.')
var result bool
if j+1 < n && p[j+1] == '*' {
// 用 0 次：跳过 p[j]p[j+1]；用 1+ 次：消耗 s[i] 继续
result = dp(i, j+2) || (firstMatch && dp(i+1, j))
} else {
// 普通字符或 '.'：当前匹配则递推
result = firstMatch && dp(i+1, j+1)
}
if result {
memo[i][j] = 1
} else {
memo[i][j] = -1
}
return result
}
return dp(0, 0)
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 44. 通配符匹配 | 困难 | 动态规划，* 独立匹配任意串 |
| 72. 编辑距离 | 中等 | 二维 DP，字符串匹配 |
| 115. 不同的子序列 | 困难 | 二维 DP，子序列计数 |
| 97. 交错字符串 | 中等 | 二维 DP，字符串交错 |
| 516. 最长回文子序列 | 中等 | 区间 DP |
| 1143. 最长公共子序列 | 中等 | 二维 DP，经典字符串匹配 |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！