LeetCode 44. 通配符匹配
目录
题目描述
题意分析
给定字符串
s和模式串p，判断p能否匹配整个s。p中除小写字母外还有两个特殊符号：?匹配任意一个字符（必须有一个，不能是零个），*匹配任意长度的字符序列，包括空序列。「匹配整个
s」这一点必须强调。不是找子串，也不是前缀匹配，而是p从头到尾用完的同时s也恰好用完。很多错误实现能通过前半段却在这里翻车。约束是两个串的长度都在 2000 以内。这意味着 $O(mn)$ 的四百万级运算完全可行，不需要费力去凑贪心的线性解法；同时它也排除了对
*的匹配长度做显式枚举的三重循环写法，那会是 $O(mn^2)$，在两千长度下就有 80 亿次，必然超时。边界情况有三类值得先想清楚。第一，
s可以为空，此时只有p全由*组成（或p也为空）才匹配。第二，p可以为空，此时只有s也为空才匹配。第三，p里可能出现连续多个*，比如"**a*"，它们在语义上等价于一个*，实现上必须能自然地处理而不出错。
解法：一维动态规划匹配前缀
核心思路
*可以匹配任意长度，若直接枚举它吞掉多少字符，会产生大量重复状态。动态规划只记录两个前缀是否匹配，把长度枚举压成常数次转移。先定义二维状态：
f[i][j]表示模式串前i个字符能否匹配字符串前j个字符。
- 普通字符或
?必须恰好消耗一个字符：
f[i][j] = f[i-1][j-1] && (p[i-1] == '?' || p[i-1] == s[j-1])。*有两种选择：
f[i][j] = f[i-1][j] || f[i][j-1]。前者表示*匹配空串，后者表示它在已经匹配前j-1个字符的基础上再吞一个字符。边界是
f[0][0] = true；空模式不能匹配非空字符串；模式前缀只有全部为*时才能匹配空串。每个状态都完整覆盖了当前模式字符的所有选择，因此转移不重不漏。由于当前行只依赖上一行和本行左侧，可以压成一维
dp[j]。这里的遍历方向由依赖决定：普通字符需要上一行的dp[j-1]，必须从右向左；*需要本行刚更新的dp[j-1]，必须从左向右。这是实现的核心。
解题步骤
- 建立长度为
n + 1的布尔数组，令dp[0] = true，表示空模式匹配空串。- 从左到右遍历模式串。
- 当前字符是
*时，令j从 1 到n，更新dp[j] = dp[j] || dp[j-1]；dp[0]保持不变，因为*可以匹配空串。- 当前字符不是
*时，令j从n到 1，按字符是否相等或为?更新；完成后将dp[0]置为 false。- 返回
dp[n]，它表示两个完整字符串是否匹配。以
s="adceb", p="*a*b"为例，处理各模式前缀后的可达长度依次为：*可达0..5，*a只可达 1，*a*可达1..5，最后的b让长度 5 可达，因此返回 true。
代码实现
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 0; i < p.length(); i++) {
char pattern = p.charAt(i);
if (pattern == '*') {
for (int j = 1; j <= n; j++) {
dp[j] = dp[j] || dp[j - 1];
}
} else {
for (int j = n; j >= 1; j--) {
dp[j] = dp[j - 1]
&& (pattern == '?' || pattern == s.charAt(j - 1));
}
dp[0] = false;
}
}
return dp[n];
}
}
func isMatch(s string, p string) bool {
n := len(s)
dp := make([]bool, n+1)
dp[0] = true
for i := 0; i < len(p); i++ {
pattern := p[i]
if pattern == '*' {
for j := 1; j <= n; j++ {
dp[j] = dp[j] || dp[j-1]
}
} else {
for j := n; j >= 1; j-- {
dp[j] = dp[j-1] && (pattern == '?' || pattern == s[j-1])
}
dp[0] = false
}
}
return dp[n]
}
复杂度分析
- 时间复杂度：$O(mn)$，其中
m、n分别是p和s的长度；每个前缀状态只转移一次。- 空间复杂度：$O(n)$，二维状态被压缩成一行。
关键点总结
*的“匹配任意长度”可拆成“匹配空串”或“在当前状态上再吞一个字符”。- 一维 DP 的更新方向取决于数据依赖：读上一行旧值就逆序，读本行新值就顺序。
dp[0]表示模式前缀能否匹配空串：遇到*保留，遇到其他字符清零。- 本题的
*是独立通配符；正则匹配第 10 题的*依附前一个字符，两者转移不同。
易错点总结
- 普通字符从左向右更新会覆盖上一行状态。例如
s="ab", p="ab"会因状态串行污染而误判；必须逆序。*从右向左更新时，true 无法沿本行传播。例如s="abc", p="*"会误判为 false；必须顺序。- 非
*分支忘记清空dp[0]，会让模式错误地跳过必须消耗字符的部分，例如s="a", p="ba"。dp[0] = false不能放在普通字符的内层循环之前，否则s="a", p="a"读取不到上一行的f[0][0]。?必须匹配恰好一个字符；只有*能匹配空串。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 10. 正则表达式匹配 | 困难 |
* 依附前一字符表示重复次数，需成对处理并向前看一位 |
| 剑指 Offer 19. 正则表达式匹配 | 困难 | 与 10 题同题，可用来对照两种 * 语义在转移式上的差异 |
| 72. 编辑距离 | 中等 | 同为两串前缀 DP，但求最小操作数而非判定，转移取三支最小值 |
| 139. 单词拆分 | 中等 | 同样是布尔可达性 DP，但枚举的是切分点而非模式字符 |