LeetCode 44困难动态规划 · 字符串
通配符匹配 图解题解
这道题到底在问什么
给字符串 s 和模式 p，判断 p 能否完整匹配 s。其中 ? 匹配任意单个字符，* 匹配任意字符序列(可以为空)。必须把整个 s 配完，整个 p 也用完。
- s
- "adceb"
- p
- "*a*b"
- 输出
- true
- 对法
- * 配空, a 配 a, * 配 "dce", b 配 b
先想最直接的笨办法
把状态定成「s 的前 i 个字符 和 p 的前 j 个字符 能不能正好配上」。一旦把每个局面的答案记进表里，重复的局面就只算一次，指数枚举立刻塌成填表。（动画第 5 步）
最优解：一步一步想明白
- 3难就难在这个 * 太灵活。你没法一眼定它吞几个，往左多吞一个还是少吞一个，都会影响后面配不配得上。先别急着写代码。
- 4最直接的想法:每个 * 都试遍「吞多少」，一路递归。逻辑没错，但 * 多了就指数爆炸，根因是同一个「s 配到哪、p 配到哪」的局面被无数条试法反复算。
- 5把状态定成「s 的前 i 个字符 和 p 的前 j 个字符 能不能正好配上」。一旦把每个局面的答案记进表里，重复的局面就只算一次，指数枚举立刻塌成填表。
- 6建一张 (len(s)+1)×(len(p)+1) 的真假表。多出来的第 0 行/第 0 列代表「空串」。递推时,普通字符和 ? 看左上角一格,* 看正上和正左两格——下面一格一格填给你看。
- 7* 的两条来路:dp[i-1][j] 表示「让 * 再多吞一个 s 字符」,dp[i][j-1] 表示「让 * 吞空、直接跳过」,两者只要有一个成立就行。普通字符 / ? 则要求当前字符配得上,且去掉这一对(看左上角)也成立。
- 8行=s 前缀长 0..5,列=p 前缀长 0..4表有 6 行 5 列。顶上一排是模式 p 的每个字符,最左一竖是 s 的每个字符,都各自在最前面补了一个 ε(空串)。dp[i][j]=true 就在第 i 行 j 列填 ✓,false 填 ✗。从左上角开始填。
- 9dp[0][0] = ✓最左上角 dp[0][0]:空字符串和空模式,啥都不用配,天然匹配。这是整张表唯一不依赖别人的地基,填 ✓。
- 10p[0]='*' → 看左边首行 = 空字符串能不能被 p 的前缀匹配。第一个字符是 *,让它吞空,就等于看它左边的 dp[0][0]=✓ → dp[0][1]=✓。只有 * 才能匹配空串。
- 11p[1]='a' ≠ 空 → ✗到列2,模式是字母 a。空字符串里一个字符都没有,普通字母没法凭空配出来 → dp[0][2]=✗。一旦首行出现非 * 字符,后面就全断了。
- 12p[2]='*' → 看左边 ✗列3 又是 *,让它吞空就看左边 dp[0][2]=✗。* 虽万能,可它救不回前面那个落单的 a → dp[0][3]=✗。
- 13p[3]='b' ≠ 空 → ✗首行最后一格是字母 b,同样配不了空串 → ✗。首行填完:✓ ✓ ✗ ✗ ✗。意思是空字符串只能被 ε 或 「*」 这两个前缀匹配。开始填正式的字符行。
- 14dp[1][1]:* 吞 a第二行对应 s 的第一个字符 a。先看列0:非空字符串配空模式,必 ✗。再看 dp[1][1],模式是 *:正上 dp[0][1]=✓(* 吞空) 或 正左 dp[1][0]=✗(* 多吞 a),只要一个 ✓ 就 ✓。
- 15dp[1][2]:a==a → 看左上列2 模式是字母 a,正好等于当前 s 字符 a。字符配得上时,这一对就「抵消」,只需看去掉它俩后的左上角 dp[0][1]=✓ → dp[1][2]=✓。
- 16dp[1][3]:* 看上/左列3 又是 *。正上 dp[0][3]=✗,但正左 dp[1][2]=✓(让这个 * 吞空、直接沿用 a 已配好的结果)→ dp[1][3]=✓。* 取「上 或 左」里任意一个 ✓。
- 17dp[1][4]:a≠b → ✗列4 模式是 b,当前 s 字符是 a,两个字母不同,普通字符配不上就直接 ✗。行 a 填完:✗ ✓ ✓ ✓ ✗。
- 18后面几行就是机械地重复这条规律。下面填字符 d、c、e、b 三行——盯住 * 那两列怎么把 ✓ 一路「传染」下来。
- 19dp[2][1]:* 看上 ✓第三行 s 字符变成 d。列0 非空配空仍 ✗。列1 是 *,正上 dp[1][1]=✓ 表示「让这个 * 多吞一个 d」→ dp[2][1]=✓。
- 20dp[2][2] = ✗列2 模式字母 a,当前 s 字符是 d,两个字母不同,普通字符配不上 → ✗。
- 21dp[2][3]:* 看上 ✓列3 又是 *。正上 dp[1][3]=✓——让第二个 * 把 d 吞进去 → dp[2][3]=✓。这个 * 开始默默吞中间的字符了。
- 22dp[2][4] = ✗,行 d 填完列4 字母 b≠d → ✗。行 d 填完:✗ ✓ ✗ ✓ ✗。两个 * 列撑住,字母列全断。
- 23dp[3][1]:* 看上 ✓第四行 s 字符 c。列1 的 * 靠正上 dp[2][1]=✓ 继续吞下 c → ✓。列0 仍 ✗。
- 24列2=✗,列3=✓列2 字母 a≠c 为 ✗;列3 * 靠正上 dp[2][3]=✓ 把 c 也吞进去 → ✓。第二个 * 已吞下 d、c。
- 25dp[3][4]=✗,行 c 填完列4 字母 b≠c → ✗。行 c 填完,和行 d 同样的形状:两个 * 列 ✓,字母列 ✗。
- 26两个 * 列继续 ✓第五行 s 字符 e。两个 * 列各自靠正上的 ✓ 把 e 也吞下,保持 ✓。第二个 * 现在已经吞了 d、c、e 三个字符。
- 27列2/列4 = ✗两个字母列 a、b 都不等于 e → ✗。行 e 填完。注意列3 这个 ✓ 一直撑到现在,意味着「a 配完后,第二个 * 把 dce 全吞了」这条路始终活着,就等最后一行的 b 来收口。
- 28dp[5][3]:* 吞 b 仍 ✓最后一行 s 字符是 b。先填前几格:列1 的 * 仍 ✓,列2 字母 a≠b 为 ✗,列3 的 * 靠正上 dp[4][3]=✓ 把 b 也吞进去 → 仍 ✓。就差最右下角那一格了。
- 29dp[5][4]:b==b → 看左上 ✓右下角 dp[5][4]:模式字母 b 正好等于 s 最后一个字符 b。字符配上,看左上角 dp[4][3]=✓(那正是「* 已吞到 e」的状态)→ dp[5][4]=✓。整张表填满。
- 30答案 = dp[5][4] = ✓ → true整张表填完,答案就藏在最右下角 dp[5][4]=✓,即 true。沿着 ✓ 回看:第一个 * 配空、a 对 a、第二个 * 吞掉 dce、b 对 b——和示例对法完全一致。
- 31每个格子只算一次、每次只看上方或左上常数个格,总共 m×n 次小计算就出答案,比挨个试 * 吞几个快出几个数量级。
- 34这里的 * 自己就能匹配任意串,是独立的万能符;正则里的 * 是「让前一个字符重复 0 次或多次」,必须跟着前一个字符理解。转移方程因此不一样,看清是哪种 *。
- 36若 dp[0][1] 不设 ✓ → 全盘崩假如忘了「首行的 * 要吞空填 ✓」,dp[0][1] 留成 ✗。那么 dp[1][1] 的两个来源都成了 ✗,这个开头的 * 彻底失效,整张表一路 ✗,最终错判 false。首行初始化绝不能省。
⚠️ 容易写错的地方
✗ 错：忘了初始化首行(空 s 配 p)
✓ 对：前导连续的 * 要把 dp[0][j] 设 ✓
如 p="*" 能配空串,漏了首行会直接判错
✗ 错：把通配 * 当成正则 *
✓ 对：本题 * 独立匹配任意串,看上/左两格
正则 * 依赖前一个字符,转移方程完全不同
✗ 错：* 转移只取了一个方向
✓ 对：dp[i-1][j] 或 dp[i][j-1] 两者取或
上=* 多吞一个,左=* 吞空,缺一种就漏解
完整代码（Python / C++ / Java）
Python
class Solution:
def isMatch(self, s, p):
m, n = len(s), len(p)
dp = [[False]*(n+1) for _ in range(m+1)]
dp[0][0] = True # 空配空
for j in range(1, n+1): # 首行:空 s
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] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1]
elif p[j-1] == '?' or p[j-1] == s[i-1]:
dp[i][j] = dp[i-1][j-1]
return dp[m][n]C++
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-1][j] || dp[i][j-1];
else if (p[j-1] == '?' || p[j-1] == s[i-1])
dp[i][j] = dp[i-1][j-1];
}
}
return dp[m][n];
}
};Java
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 j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char pc = p.charAt(j - 1);
if (pc == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
} else if (pc == '?' || pc == s.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}复杂度
时间复杂度
O(m·n)
m=len(s)、n=len(p);表共 (m+1)(n+1) 个格,每格只算一次、常数次比较
空间复杂度
O(m·n)
开整张二维表;因每格只依赖上一行与本行左边,可滚动压成 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 通配符匹配 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
空间能优化到 O(n) 吗?+
能。dp[i][j] 只依赖上一行 dp[i-1][*] 和本行已填的左边,所以用一维数组按行滚动更新即可,把 O(mn) 压成 O(n)。注意更新顺序和保存左上角的旧值。
有没有比 DP 更快的解法?+
有双指针贪心法:记住最近一个 * 的位置和它当时匹配到的 s 位置,失配就回退让 * 多吞一个。平均接近 O(m+n)、最坏 O(mn),空间 O(1),但更难写对。
本题和 LC10 正则匹配的核心区别?+
本题 * 独立匹配任意串,转移看上/左;LC10 的 * 修饰前一个字符表示重复,要把『字符+*』当一个单元处理,转移方程更复杂。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 通配符匹配 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。