通配符匹配
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个输入字符串 s 和一个字符模式 p，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
'?'可以匹配任何单个字符。'*'可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1
示例 2
示例 3
模拟答题者思考
1. 最直接：遇到 '*' 就递归枚举「匹配 0 个 / 1 个 / 2 个…」字符，指数级回溯，s=2000, p=2000 会超时。
2. 重复在哪里？同样的 (i, j)（还剩多少 s、还剩多少 p）会被反复访问——典型重叠子问题。
3. 子问题定义：「s 的前 i 个能否被 p 的前 j 个完整匹配？」自然落到二维 DP。与正则题不同，这里的 '*' 不绑定前一个字符，可独立匹配任意长度序列。
4. 难点在 '*'：它可以匹配空（直接看 dp[i][j-1]，跳过这个 *），也可以再多吃 s 的一个字符（看 dp[i-1][j]，* 仍留在模式里继续匹配后续）。
5. 边界：dp[0][0]=true；空串匹配纯 * 模式时，dp[0][j] = dp[0][j-1]（只有 * 能匹配空序列）。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dp[i][j] | bool[][] | 定义：s 的前 i 个字符能否被 p 的前 j 个字符完整匹配维护：只依赖更小的子问题 dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]更新：若 p[j-1] 是普通字符或 '?'，看当前位能否对上并继承 dp[i-1][j-1]；若是 '*'，先尝试「匹配空序列」(dp[i][j-1])，再尝试「多吃掉 s 的一个字符」(dp[i-1][j]) |
i, j | int | 定义：分别表示已消耗的 s 前缀长度、p 前缀长度维护： i 从 0 到 m，j 从 0 到 n 递增填表更新：答案在 dp[m][n] |
落码步骤
1. 建表 dp[(m+1)][(n+1)]，dp[0][0]=true
2. 初始化第 0 行：若 p[j-1]=='*'，则 dp[0][j] = dp[0][j-1]（空串被 * 吃掉）
3. 双重循环填表：若 p[j-1]=='*'，dp[i][j] = dp[i][j-1] or dp[i-1][j]
4. 否则若 p[j-1]=='?' 或 s[i-1]==p[j-1]，dp[i][j] = dp[i-1][j-1]
5. 返回 dp[m][n]
代码实现
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
# dp[i][j]：s 前 i 个字符能否被 p 前 j 个完整匹配
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# 空串匹配纯 * 模式：* 可匹配空序列
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
# 匹配空序列（跳过 *）或多吃 s 的一个字符
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p[j - 1] == '?' or s[i - 1] == p[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 j = 1; j <= n; j++) {
if (p[j - 1] == '*')
dp[0][j] = dp[0][j - 1];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
// 时间 O(mn)，空间 O(mn)，可滚动数组优化到 O(n)复杂度分析
O(m × n)（m、s 长度；n、p 长度）
O(m × n) / O(n)（可滚动数组优化）
常见坑
通配符 '*' 与正则 '*' 不同：它不绑定前一个字符，转移是 dp[i][j-1]（跳过 *）和 dp[i-1][j]（* 继续吃字符），不是 dp[i][j-2]。
空串行初始化不能漏：像 "***"、"a*b*" 对空串也应为 true，只有 p[j-1]=='*' 时才能 dp[0][j]=dp[0][j-1]。
'?' 只能匹配一个字符，不能匹配空；写 dp[i][j]=dp[i][j-1] 会误判。
必测边界 Case
s = "aa", p = "a" → false（模式无法覆盖整个串）
s = "aa", p = "*" → true
s = "cb", p = "?a" → false（? 匹配 c，但 a 无法匹配 b）
s = "", p = "***" → true
s = "adceb", p = "*a*b" → true（* 匹配空，a 匹配 a，* 匹配 dce，b 匹配 b）