10. 正则表达式匹配
题目描述
输入字符串 s 和模式串 p，实现一个简化的正则匹配，只支持两种特殊字符：
'.' 可以匹配任意一个字符；'*' 表示紧挨在它前面的那个字符可以重复出现任意次，包括 0 次。
匹配必须覆盖整个 s，只匹配其中一部分不算。能完整匹配时返回 true，否则返回 false。
示例 1
输入：s = "aa", p = "a" 输出：false
解释："a" 只能匹配一个字符，无法覆盖整个 "aa"。
示例 2
输入：s = "aa", p = "a*" 输出：true
解释："a*" 中的 a 可以重复两次，正好得到 "aa"。
示例 3
输入：s = "ab", p = ".*" 输出：true
解释：".*" 表示任意字符重复任意次，可以匹配任何字符串。
数据范围
1 <= s.length <= 201 <= p.length <= 20s只含小写英文字母。p只含小写英文字母、'.'和'*'。- 每个
'*'前面一定有一个可以重复的有效字符。
解题思路：自底向上动态规划
设 dp[i][j] 表示 s 的前 i 个字符能否被 p 的前 j 个字符匹配。看 p 的最后一个字符 p[j-1]：如果是普通字符或 .，它必须和 s[i-1] 对上，然后看 dp[i-1][j-1]。如果是 *，它和前一个字符 x 组成 x*，有两种用法：用 0 次，直接丢掉 x*，看 dp[i][j-2]；或者在 x 能匹配 s[i-1] 时让 x* 吃掉 s[i-1]，但 x* 还留着可以继续吃，看 dp[i-1][j]。
为什么正确
dp[i][j] 只依赖左边两格 dp[i][j-2]、上一格 dp[i-1][j] 和左上 dp[i-1][j-1]，所以按行从左到右填表时依赖都已算好。
复杂度分析
时间 O(mn)，空间 O(mn)。
易错点
把 * 当成独立的通配符，或者忘了第 0 行也要填。像 a*b* 这样的模式可以匹配空串，所以 i 必须从 0 开始循环。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 2]
if i > 0 and p[j - 2] in (s[i - 1], '.'):
dp[i][j] = dp[i][j] or dp[i - 1][j]
elif i > 0 and p[j - 1] in (s[i - 1], '.'):
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]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++) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2];
if (i > 0 && (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.')) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else if (i > 0 && (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.')) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2];
if (i > 0 && (p[j - 2] == s[i - 1] || p[j - 2] == '.')) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else if (i > 0 && (p[j - 1] == s[i - 1] || p[j - 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
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 && (p[j-2] == s[i-1] || p[j-2] == '.') {
dp[i][j] = dp[i][j] || dp[i-1][j]
}
} else if i > 0 && (p[j-1] == s[i-1] || p[j-1] == '.') {
dp[i][j] = dp[i-1][j-1]
}
}
}
return dp[m][n]
}var isMatch = function(s, p) {
const m = s.length, n = p.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
dp[0][0] = true;
for (let i = 0; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (p[j - 1] === '*') {
dp[i][j] = dp[i][j - 2];
if (i > 0 && (p[j - 2] === s[i - 1] || p[j - 2] === '.')) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else if (i > 0 && (p[j - 1] === s[i - 1] || p[j - 1] === '.')) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
};function isMatch(s: string, p: string): boolean {
const m = s.length, n = p.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
dp[0][0] = true;
for (let i = 0; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (p[j - 1] === '*') {
dp[i][j] = dp[i][j - 2];
if (i > 0 && (p[j - 2] === s[i - 1] || p[j - 2] === '.')) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else if (i > 0 && (p[j - 1] === s[i - 1] || p[j - 1] === '.')) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}其他解法
同一个状态转移的两种实现：自顶向下的记忆化递归从暴力搜索自然演进而来，自底向上填表没有递归开销。复杂度相同。
解法 2：记忆化递归 时间 O(mn)，空间 O(mn)
dfs(i, j) 表示 s[i:] 能否匹配 p[j:]。先算当前字符是否匹配 first。若 p[j+1] 是 '*'，有两种选择：跳过「x*」即 dfs(i, j+2)，或在 first 成立时用它吃掉一个字符即 dfs(i+1, j)；否则必须 first 成立且 dfs(i+1, j+1)。用表缓存每个 (i, j) 的结果。
从「怎么逐步匹配」的暴力递归自然推导而来，转移比填表更好理解，且只计算实际访问到的状态。代价是递归栈开销，极长输入时可能栈溢出。
from functools import lru_cache
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
@lru_cache(maxsize=None)
def dfs(i, j):
if j == n:
return i == m
first = i < m and p[j] in (s[i], '.')
if j + 1 < n and p[j + 1] == '*':
return dfs(i, j + 2) or (first and dfs(i + 1, j))
return first and dfs(i + 1, j + 1)
return dfs(0, 0)class Solution {
private String s, p;
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) Arrays.fill(row, -1);
return dfs(0, 0);
}
private boolean dfs(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 first = i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
boolean ans;
if (j + 1 < n && p.charAt(j + 1) == '*') ans = dfs(i, j + 2) || (first && dfs(i + 1, j));
else ans = first && dfs(i + 1, j + 1);
memo[i][j] = ans ? 1 : 0;
return ans;
}
}class Solution {
public:
string s, p;
vector<vector<int>> memo;
bool isMatch(string s, string p) {
this->s = s;
this->p = p;
memo.assign(s.size() + 1, vector<int>(p.size() + 1, -1));
return dfs(0, 0);
}
bool dfs(int i, int j) {
int m = s.size(), n = p.size();
if (j == n) return i == m;
if (memo[i][j] != -1) return memo[i][j];
bool first = i < m && (p[j] == s[i] || p[j] == '.');
bool ans;
if (j + 1 < n && p[j + 1] == '*') ans = dfs(i, j + 2) || (first && dfs(i + 1, j));
else ans = first && dfs(i + 1, j + 1);
memo[i][j] = ans;
return ans;
}
};func isMatch(s string, p string) bool {
m, n := len(s), len(p)
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(i, j int) bool
dfs = func(i, j int) bool {
if j == n {
return i == m
}
if memo[i][j] != -1 {
return memo[i][j] == 1
}
first := i < m && (p[j] == s[i] || p[j] == '.')
var ans bool
if j+1 < n && p[j+1] == '*' {
ans = dfs(i, j+2) || (first && dfs(i+1, j))
} else {
ans = first && dfs(i+1, j+1)
}
if ans {
memo[i][j] = 1
} else {
memo[i][j] = 0
}
return ans
}
return dfs(0, 0)
}var isMatch = function(s, p) {
const m = s.length, n = p.length;
const memo = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(-1));
const dfs = (i, j) => {
if (j === n) return i === m;
if (memo[i][j] !== -1) return memo[i][j] === 1;
const first = i < m && (p[j] === s[i] || p[j] === '.');
let ans;
if (j + 1 < n && p[j + 1] === '*') ans = dfs(i, j + 2) || (first && dfs(i + 1, j));
else ans = first && dfs(i + 1, j + 1);
memo[i][j] = ans ? 1 : 0;
return ans;
};
return dfs(0, 0);
};function isMatch(s: string, p: string): boolean {
const m = s.length, n = p.length;
const memo: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(-1));
const dfs = (i: number, j: number): boolean => {
if (j === n) return i === m;
if (memo[i][j] !== -1) return memo[i][j] === 1;
const first = i < m && (p[j] === s[i] || p[j] === '.');
let ans: boolean;
if (j + 1 < n && p[j + 1] === '*') ans = dfs(i, j + 2) || (first && dfs(i + 1, j));
else ans = first && dfs(i + 1, j + 1);
memo[i][j] = ans ? 1 : 0;
return ans;
};
return dfs(0, 0);
};