LeetCode 44. 通配符匹配
题目描述
题意分析
判断模式串
p能否完整匹配文本串s，要求覆盖双方的全部字符，不能只匹配文本中的一段。普通字母只能匹配相同字母，?恰好匹配一个任意字符，*可以匹配任意长度的字符序列，包括空串。两个字符串都可能为空。本题的
*是独立通配符，不依附在前一个字符上；它的含义与正则表达式中的重复符号不同，转移方式也不同。
解法：一维动态规划匹配前缀
核心思路
[!blue]
先定义二维状态
F[i][j]：模式前i个字符能否匹配文本前j个字符。初始F[0][0] = true，空模式不能匹配非空文本。每加入一个模式字符，就计算一行新的匹配状态。如果当前模式字符是普通字母或
?，它必须消耗文本最后一个字符。只有这两个字符能够匹配，且更短的两个前缀F[i - 1][j - 1]已经匹配，当前状态才为真。普通字符要求相等，?则不限制文本字符是什么。如果当前字符是
*，分为两种情况：让它匹配空串，就继承F[i - 1][j]；让它匹配至少一个字符，可以先用当前模式匹配前j - 1个字符，再让这个星号多接一个字符，读取F[i][j - 1]。因此星号的转移是这两个状态取逻辑或，已经覆盖了所有可能的匹配长度。只保存一行
dp时，要按依赖选择更新方向。普通字符和?需要上一行的dp[j - 1]，所以从右向左更新，避免它提前被覆盖。星号需要本行已更新的dp[j - 1]，因此从左向右更新；此时原位置的dp[j]仍是上一行状态，执行dp[j] = dp[j] || dp[j - 1]即可。
dp[0]表示当前模式前缀能否匹配空文本。遇到星号可以保持原值，遇到其他字符则必须变为假。但清零必须放在该行的内层循环之后，因为更新j = 1时还可能需要上一行的dp[0]。全部模式字符处理完后，返回dp[n]。
解题步骤
- 创建长度为
n + 1的布尔数组，令dp[0] = true，其余为假。- 从左到右遍历模式字符。
- 遇到
*，从j = 1到n更新dp[j] = dp[j] || dp[j - 1]，保持dp[0]不变。- 遇到普通字符或
?，从j = n到1，根据旧dp[j - 1]与当前字符能否匹配更新状态；循环结束后令dp[0] = false。- 返回
dp[n]，表示完整模式与完整文本是否匹配。
代码实现
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)$，其中
m、n分别是模式和文本长度。核心转移为 $O(mn)$，初始化数组及扫描模式另需线性开销；当字符串非空时通常简写为 $O(mn)$。- 空间复杂度：$O(n + 1)$，保存长度为
n + 1的一维状态，不保存全部二维前缀状态。
关键点总结
[!green]
- 先按前缀定义二维转移，再根据旧行或新行的依赖压缩空间，更新方向不能统一套用。
- 星号“不匹配字符”和“继续匹配一个字符”两种选择的逻辑或，覆盖任意长度匹配。
- 空文本只能被全是星号的模式前缀匹配；
dp[0]专门维护这个边界。
易错点总结
[!yellow]
- 普通字符正序更新，会读取本轮刚改写的左侧状态，错误地让同一模式字符参与多次匹配。
- 星号逆序更新，无法把本行已经可达的前缀继续向右扩展，限制了星号的匹配长度。
- 遇到非星号时不清零
dp[0]，会把必须消耗字符的模式部分当成能够匹配空串。- 在普通字符内层循环之前清零
dp[0]，又会丢掉更新第一个文本字符所需的旧状态。?不允许匹配空串；最终必须读取完整长度的dp[n]，不能发现某个短前缀匹配就返回真。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 10. 正则表达式匹配 | 困难 | 星号语义不同：本题星号可匹配任意字符串，正则星号只能重复它前面的元素。 |