题目描述
思路解析
一句话答案：LeetCode 10 正则表达式匹配的标准解法是二维动态规划：dp[i][j] 表示 s 的前 i 个字符能否被模式 p 的前 j 位完整配通。难点全在星号——把「字符+*」捆成整体，要么让该字符出现 0 次（看 dp[i][j-2]），要么再吃一个字符（看 dp[i-1][j]），两条路通一条即可。时间与空间均 O(m·n)。
正则表达式匹配这道题在问什么
给字符串 s 和模式 p，p 只含小写字母、点号和星号：点号匹配任意单个字符；星号表示它前面那一个字符可以出现 0 次或任意多次。要求 p 必须完整匹配整个 s，不是找子串。最容易先入为主的误解是把星号当成 shell 里的通配符——a* 的意思是「任意多个 a」，不是「任意字符串」，理解错这一点后面全错。
为什么从左到右直接配会失败，非得用 DP
直觉做法是拿两个指针从左往右一路配过去。但碰到星号就卡壳了：x* 到底该吃几个字符，当场根本定不下来。拿示例 s = "aab"、p = "c*a*b" 来说，c* 必须选择吃 0 个字符，a* 必须选择吃 2 个，才能整体配通——而每个选择的对错要看后面的匹配结果才知道，局部贪心没有依据。
选择当场定不下来，就只能把所有分支都试一遍，这是递归回溯；而回溯过程中「s 剩后半段、p 剩后半段」这样的子问题会被反复算到，重叠子问题加上答案只由双方剩余位置决定，正是动态规划的地盘。
dp[i][j] 的状态定义为什么是双前缀
定义 dp[i][j] 为：s 的前 i 个字符能否被 p 的前 j 位模式完整配通，值是布尔。用「前缀对前缀」做状态，是因为匹配过程天然从左往右推进，任何一个匹配方案在中途截断，剩下的都是「某前缀对某前缀」的判定。起点 dp[0][0] = true，空串配空模式当然成立。
第 0 行（s 为空）不全是 false：像 c* 或 a*b* 这样的模式可以让字符出现 0 次而配上空串，所以 dp[0][j] 要照常按星号规则推。这也是很多人第一次写这题时漏掉的初始化。
星号的两条转移路为什么恰好不重不漏
当 p 的第 j 位是星号时，把 p[j-2] 和这个星号捆成整体「x*」，它对最终匹配的贡献只有两类。第一类：x 出现 0 次，整个 x* 等于没写，成不成立看 dp[i][j-2]。第二类：x 至少出现 1 次，那就让它把 s 当前这个字符吃掉——前提是 x 真配得上 s[i-1]（相等或 x 是点号），吃完后 s 往前退一格、模式停在原地（x* 还能继续吃），所以看 dp[i-1][j]。任何一种匹配方案里 x 出现的次数非 0 即正，两条路恰好覆盖全部情况，取或即可。
当 p 的第 j 位是普通字符或点号时更简单：它必须吃掉 s 当前字符，配得上就双双前进一格，看左上方 dp[i-1][j-1]；配不上直接 false。
复杂度多少，哪些坑最容易踩
表共 (m+1) × (n+1) 格，每格转移 O(1)，时间 O(m·n)；空间 O(m·n)，由于每格只依赖上一行和本行左侧，可以滚动数组压到 O(n)。
三个高频错误：一是忘了星号可以让前字符出现 0 次，漏掉 dp[i][j-2] 这条路，c* 配空串这类用例立刻挂；二是「再吃一个」时忘了先判 p[j-2] 能否配上 s[i-1]，星号不能硬吃配不上的字符；三是把「再吃一个」的转移写成 dp[i-1][j-2]——吃字符时模式不前进，列号必须留在 j。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一句：碰到普通字符或 “.”，就斜着看左上一格；碰到 “*”，就看两条路——“前字符出现 0 个”（看左边隔一格）或“前字符再吃 1 个”（看正上一格）。
左上角先点亮 ✓：s 取 0 个字符、p 取 0 个字符，空配空当然成立。其余格从这里逐格推。
判 dp[0][1]：s 是空串，但模式 'c' 是个要吃字符的普通位，没字符给它配，所以 ✗。
落子：dp[0][1] = ✗。当前位配上了但左上一格不成立，这个前缀配不通。
判 dp[0][2]：s 是空串。模式 "c*" 只能让 c 出现 0 个（路A），看左隔一格 dp[0][0] 是否成立。
落子：dp[0][2] = ✓。让 c 出现 0 个就能成立。
判 dp[0][3]：s 是空串，但模式 'a' 是个要吃字符的普通位，没字符给它配，所以 ✗。
落子：dp[0][3] = ✗。当前位配上了但左上一格不成立，这个前缀配不通。
判 dp[0][4]：s 是空串。模式 "a*" 只能让 a 出现 0 个（路A），看左隔一格 dp[0][2] 是否成立。
落子：dp[0][4] = ✓。让 a 出现 0 个就能成立。
判 dp[0][5]：s 是空串，但模式 'b' 是个要吃字符的普通位，没字符给它配，所以 ✗。
落子：dp[0][5] = ✗。当前位配上了但左上一格不成立，这个前缀配不通。
第 0 列是“模式 p 为空”的情况：s 还有 1 个字符没地方配，所以 dp[1][0] = ✗。
判 dp[1][1]：模式是 'c'，要去配 s 当前的 'a'。'c' 和 'a' 不同，配不上。配上了就斜看左上一格 dp[0][0]，前面也得已经配通。
落子：dp[1][1] = ✗。当前位字符配不上，这个前缀配不通。
判 dp[1][2]：模式走到 "c*"。两条路——路A让 c 出现 0 个（直接跳过这两位，看左隔一格）；路B让 c 再吃当前的 'a'（要 'c' 配得上 'a'，再看正上一格）。任一条通，这格就 ✓。
落子：dp[1][2] = ✗。出现 0 个和再吃一个两条路都走不通。
判 dp[1][3]：模式是 'a'，要去配 s 当前的 'a'。'a' 和 'a' 相同，配上。配上了就斜看左上一格 dp[0][2]，前面也得已经配通。
落子：dp[1][3] = ✓。当前位配上了，且左上一格成立，前 1 个字符被前 3 位模式配通。
判 dp[1][4]：模式走到 "a*"。两条路——路A让 a 出现 0 个（直接跳过这两位，看左隔一格）；路B让 a 再吃当前的 'a'（要 'a' 配得上 'a'，再看正上一格）。任一条通，这格就 ✓。
落子：dp[1][4] = ✓。让 a 再吃一个 'a'，前缀配通了。
判 dp[1][5]：模式是 'b'，要去配 s 当前的 'a'。'b' 和 'a' 不同，配不上。配上了就斜看左上一格 dp[0][4]，前面也得已经配通。
落子：dp[1][5] = ✗。当前位字符配不上，这个前缀配不通。
第 0 列是“模式 p 为空”的情况：s 还有 2 个字符没地方配，所以 dp[2][0] = ✗。
判 dp[2][1]：模式是 'c'，要去配 s 当前的 'a'。'c' 和 'a' 不同，配不上。配上了就斜看左上一格 dp[1][0]，前面也得已经配通。
落子：dp[2][1] = ✗。当前位字符配不上，这个前缀配不通。
判 dp[2][2]：模式走到 "c*"。两条路——路A让 c 出现 0 个（直接跳过这两位，看左隔一格）；路B让 c 再吃当前的 'a'（要 'c' 配得上 'a'，再看正上一格）。任一条通，这格就 ✓。
落子：dp[2][2] = ✗。出现 0 个和再吃一个两条路都走不通。
判 dp[2][3]：模式是 'a'，要去配 s 当前的 'a'。'a' 和 'a' 相同，配上。配上了就斜看左上一格 dp[1][2]，前面也得已经配通。
落子：dp[2][3] = ✗。当前位配上了但左上一格不成立，这个前缀配不通。
判 dp[2][4]：模式走到 "a*"。两条路——路A让 a 出现 0 个（直接跳过这两位，看左隔一格）；路B让 a 再吃当前的 'a'（要 'a' 配得上 'a'，再看正上一格）。任一条通，这格就 ✓。
落子：dp[2][4] = ✓。让 a 再吃一个 'a'，前缀配通了。
判 dp[2][5]：模式是 'b'，要去配 s 当前的 'a'。'b' 和 'a' 不同，配不上。配上了就斜看左上一格 dp[1][4]，前面也得已经配通。
落子：dp[2][5] = ✗。当前位字符配不上，这个前缀配不通。
第 0 列是“模式 p 为空”的情况：s 还有 3 个字符没地方配，所以 dp[3][0] = ✗。
判 dp[3][1]：模式是 'c'，要去配 s 当前的 'b'。'c' 和 'b' 不同，配不上。配上了就斜看左上一格 dp[2][0]，前面也得已经配通。
落子：dp[3][1] = ✗。当前位字符配不上，这个前缀配不通。
判 dp[3][2]：模式走到 "c*"。两条路——路A让 c 出现 0 个（直接跳过这两位，看左隔一格）；路B让 c 再吃当前的 'b'（要 'c' 配得上 'b'，再看正上一格）。任一条通，这格就 ✓。
落子：dp[3][2] = ✗。出现 0 个和再吃一个两条路都走不通。
判 dp[3][3]：模式是 'a'，要去配 s 当前的 'b'。'a' 和 'b' 不同，配不上。配上了就斜看左上一格 dp[2][2]，前面也得已经配通。
落子：dp[3][3] = ✗。当前位字符配不上，这个前缀配不通。
判 dp[3][4]：模式走到 "a*"。两条路——路A让 a 出现 0 个（直接跳过这两位，看左隔一格）；路B让 a 再吃当前的 'b'（要 'a' 配得上 'b'，再看正上一格）。任一条通，这格就 ✓。
落子：dp[3][4] = ✗。出现 0 个和再吃一个两条路都走不通。
判 dp[3][5]：模式是 'b'，要去配 s 当前的 'b'。'b' 和 'b' 相同，配上。配上了就斜看左上一格 dp[2][4]，前面也得已经配通。
落子：dp[3][5] = ✓。当前位配上了，且左上一格成立，前 3 个字符被前 5 位模式配通。
右下角 dp[3][5] = ✓：用完 s 的全部 3 个字符、p 的全部 5 位模式，正好完整匹配，所以答案是 true。
边界先想清，尤其“*”配 0 个的情形。
两个高频追问，都卡在对 “*” 的理解。
参考代码
def isMatch(s, p): m, n = len(s), len(p) dp = [[False]*(n+1) for _ in range(m+1)] dp[0][0] = True for i in range(m+1): for j in range(1, n+1): if p[j-1] == "*": dp[i][j] = dp[i][j-2] if i and p[j-2] in (s[i-1], "."): dp[i][j] = dp[i][j] or dp[i-1][j] elif i and p[j-1] in (s[i-1], "."): dp[i][j] = dp[i-1][j-1] return dp[m][n]复杂度
- 时间：O(m·n)，每格 O(1)，共 (m+1)×(n+1) 格
- 空间：O(m·n)，整表；每格只依赖上格/左上/左隔一格，可滚动到 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么 “*” 看的是 dp[i-1][j] 而不是 dp[i-1][j-2]？
追问能用递归 + 记忆化做吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大正方形
LeetCode 221 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题