通配符匹配

难就难在这个 * 太灵活。你没法一眼定它吞几个，往左多吞一个还是少吞一个，都会影响后面配不配得上。先别急着写代码。

最直接的想法:每个 * 都试遍「吞多少」，一路递归。逻辑没错，但 * 多了就指数爆炸，根因是同一个「s 配到哪、p 配到哪」的局面被无数条试法反复算。

把状态定成「s 的前 i 个字符 和 p 的前 j 个字符 能不能正好配上」。一旦把每个局面的答案记进表里，重复的局面就只算一次，指数枚举立刻塌成填表。

建一张 (len(s)+1)×(len(p)+1) 的真假表。多出来的第 0 行/第 0 列代表「空串」。递推时,普通字符和 ? 看左上角一格,* 看正上和正左两格——下面一格一格填给你看。

* 的两条来路:dp[i-1][j] 表示「让 * 再多吞一个 s 字符」,dp[i][j-1] 表示「让 * 吞空、直接跳过」,两者只要有一个成立就行。普通字符 / ? 则要求当前字符配得上,且去掉这一对(看左上角)也成立。

建表 · 行列含义：表有 6 行 5 列。顶上一排是模式 p 的每个字符,最左一竖是 s 的每个字符,都各自在最前面补了一个 ε(空串)。dp[i][j]=true 就在第 i 行 j 列填 ✓,false 填 ✗。从左上角开始填。

地基 · 空串配空串：最左上角 dp[0][0]:空字符串和空模式,啥都不用配,天然匹配。这是整张表唯一不依赖别人的地基,填 ✓。

首行 · 空 s 配 p 前缀(列1)：首行 = 空字符串能不能被 p 的前缀匹配。第一个字符是 *,让它吞空,就等于看它左边的 dp[0][0]=✓ → dp[0][1]=✓。只有 * 才能匹配空串。

首行 · 列2 是字母 a：到列2,模式是字母 a。空字符串里一个字符都没有,普通字母没法凭空配出来 → dp[0][2]=✗。一旦首行出现非 * 字符,后面就全断了。

首行 · 列3 又是 *：列3 又是 *,让它吞空就看左边 dp[0][2]=✗。* 虽万能,可它救不回前面那个落单的 a → dp[0][3]=✗。

首行 · 列4 字母 b：首行最后一格是字母 b,同样配不了空串 → ✗。首行填完:✓ ✓ ✗ ✗ ✗。意思是空字符串只能被 ε 或 「*」 这两个前缀匹配。开始填正式的字符行。

行 a · 列1 是 *：第二行对应 s 的第一个字符 a。先看列0:非空字符串配空模式,必 ✗。再看 dp[1][1],模式是 *:正上 dp[0][1]=✓(* 吞空) 或 正左 dp[1][0]=✗(* 多吞 a),只要一个 ✓ 就 ✓。

行 a · 列2 字母 a 对上：列2 模式是字母 a,正好等于当前 s 字符 a。字符配得上时,这一对就「抵消」,只需看去掉它俩后的左上角 dp[0][1]=✓ → dp[1][2]=✓。

行 a · 列3 是 *：列3 又是 *。正上 dp[0][3]=✗,但正左 dp[1][2]=✓(让这个 * 吞空、直接沿用 a 已配好的结果)→ dp[1][3]=✓。* 取「上 或 左」里任意一个 ✓。

行 a · 列4 字母 b：列4 模式是 b,当前 s 字符是 a,两个字母不同,普通字符配不上就直接 ✗。行 a 填完:✗ ✓ ✓ ✓ ✗。

后面几行就是机械地重复这条规律。下面填字符 d、c、e、b 三行——盯住 * 那两列怎么把 ✓ 一路「传染」下来。

行 d · 列1 的 * 吞下 d：第三行 s 字符变成 d。列0 非空配空仍 ✗。列1 是 *,正上 dp[1][1]=✓ 表示「让这个 * 多吞一个 d」→ dp[2][1]=✓。

行 d · 列2 字母 a≠d：列2 模式字母 a,当前 s 字符是 d,两个字母不同,普通字符配不上 → ✗。

行 d · 列3 的 * 也吞 d：列3 又是 *。正上 dp[1][3]=✓——让第二个 * 把 d 吞进去 → dp[2][3]=✓。这个 * 开始默默吞中间的字符了。

行 d · 列4 字母 b≠d：列4 字母 b≠d → ✗。行 d 填完:✗ ✓ ✗ ✓ ✗。两个 * 列撑住,字母列全断。

行 c · 列1 的 * 吞 c：第四行 s 字符 c。列1 的 * 靠正上 dp[2][1]=✓ 继续吞下 c → ✓。列0 仍 ✗。

行 c · 列3 的 * 吞 c：列2 字母 a≠c 为 ✗;列3 * 靠正上 dp[2][3]=✓ 把 c 也吞进去 → ✓。第二个 * 已吞下 d、c。

行 c · 列4 字母 b≠c：列4 字母 b≠c → ✗。行 c 填完,和行 d 同样的形状:两个 * 列 ✓,字母列 ✗。

行 e · 列1、列3 的 * 吞 e：第五行 s 字符 e。两个 * 列各自靠正上的 ✓ 把 e 也吞下,保持 ✓。第二个 * 现在已经吞了 d、c、e 三个字符。

行 e · 字母列 ✗,行 e 填完：两个字母列 a、b 都不等于 e → ✗。行 e 填完。注意列3 这个 ✓ 一直撑到现在,意味着「a 配完后,第二个 * 把 dce 全吞了」这条路始终活着,就等最后一行的 b 来收口。

行 b · 列3 撑住 *：最后一行 s 字符是 b。先填前几格:列1 的 * 仍 ✓,列2 字母 a≠b 为 ✗,列3 的 * 靠正上 dp[4][3]=✓ 把 b 也吞进去 → 仍 ✓。就差最右下角那一格了。

行 b · 列4 字母 b 收口：右下角 dp[5][4]:模式字母 b 正好等于 s 最后一个字符 b。字符配上,看左上角 dp[4][3]=✓(那正是「* 已吞到 e」的状态)→ dp[5][4]=✓。整张表填满。

读答案 · 最右下角：整张表填完,答案就藏在最右下角 dp[5][4]=✓,即 true。沿着 ✓ 回看:第一个 * 配空、a 对 a、第二个 * 吞掉 dce、b 对 b——和示例对法完全一致。

每个格子只算一次、每次只看上方或左上常数个格,总共 m×n 次小计算就出答案,比挨个试 * 吞几个快出几个数量级。

这里的 * 自己就能匹配任意串,是独立的万能符;正则里的 * 是「让前一个字符重复 0 次或多次」,必须跟着前一个字符理解。转移方程因此不一样,看清是哪种 *。

雷区实演 · 漏了首行的 *：假如忘了「首行的 * 要吞空填 ✓」,dp[0][1] 留成 ✗。那么 dp[1][1] 的两个来源都成了 ✗,这个开头的 * 彻底失效,整张表一路 ✗,最终错判 false。首行初始化绝不能省。

边界三连：先想空串(dp[0][0]=✓)、纯星号(首行一路 ✓)、长度不够(s 没配完)。这三种小例子能验证首行初始化和右下角读法都对。

面试追问：把「* 只依赖上一行 → 可滚动数组 → O(n) 空间」和「贪心双指针 O(1) 空间」讲清楚,是这题面试的加分点。