算法通关手册题解：LeetCode 10 正则表达式匹配——基于二维动态规划的 `.` 与 `*` 通配模式匹配

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册AlgoNote」0010. 正则表达式匹配题解 的深度展开版。题目要求实现一个仅支持.匹配任意单个字符与*匹配零个或多个前一元素的简化版正则匹配引擎是典型的双串模糊匹配问题。读完本文你将掌握如何用二维布尔 DP 表完整推导并落地该题解如何正确处理*的「匹配 0 次 / 1 次 / 多次」三种语义以及它与 LeetCode 44 通配符匹配之间的本质差异。1. 题目概述题目编号0010LeetCode 10标签递归、字符串、动态规划难度困难题目大意给定一个字符串s和一个字符模式串p实现一个支持.和*的正则表达式匹配。两个字符串完全匹配才算匹配成功匹配成功返回True否则返回False。.匹配任意单个字符。*匹配零个或多个前面的那一个元素。数据范围与约束约束项取值字符串长度$1 \le s.length \le 20$模式串长度$1 \le p.length \le 30$字符串s只包含a~z的小写字母模式串p只包含a~z的小写字母以及字符.和*有效性保证每次出现*时前面都匹配到有效的字符这里的「保证每次出现字符*时前面都匹配到有效的字符」意味着*不会出现在模式串首位也不会连续出现形如***总是紧跟在一个普通字符或.之后这使得我们可以安全地把p[j-2]视为*所作用的前一元素。1.1 示例示例 1输入s aa, p a* 输出True 解释因为 * 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 a。因此字符串 aa 可被视为 a 重复了一次。示例 2输入s aa, p a 输出False 解释a 无法匹配 aa 整个字符串。注意本题要求的是完全匹配即模式串必须覆盖整个字符串s不存在「子串包含」的宽松语义。这正是它区别于一般字符串查找算法如 KMP、Boyer-Moore 等精确匹配算法的地方——那些算法无法处理*带来的变长匹配因此需要另辟蹊径。2. 题目分析为什么选择动态规划正则匹配天然具备重叠子问题与最优子结构特征判断s的前i个字符与p的前j个字符是否匹配可以分解为判断更短前缀之间的匹配关系且这些更短的子问题在递推过程中会被反复引用。这与「算法通关手册」动态规划基础 中归纳的 DP 三要素最优子结构、重叠子问题、无后效性完全吻合重叠子问题dp[i][j]会被多个后续状态引用例如dp[i][j]同时出现在dp[i1][j]、dp[i][j1]的转移来源中无后效性一旦dp[i][j]确定后续决策不会再回头修改它按阶段递推按照「字符串结尾位置」划分阶段自底向上填表。此外在「算法通关手册」双串线性 DP 的分类中本题与编辑距离LeetCode 72同属双串线性 DP 的字符串模糊匹配问题两个字符串各用一个指针推进用dp[i][j]记录两个前缀之间的某种关系是否匹配 / 最小操作次数。掌握了这类问题的「状态设计 分类讨论」范式再看本题就会非常顺。3. 思路 1动态规划完整推导3.1 阶段划分按照两个字符串的结尾位置进行阶段划分s的前缀长度i从0增长到size_sp的前缀长度j从0增长到size_p。每一个(i, j)组合就是一个阶段阶段的推进顺序是外层遍历i、内层遍历j。3.2 定义状态定义状态dp[i][j]表示字符串s的前i个字符与字符串p的前j个字符是否匹配其值为布尔量True/False。这里采用「前i个字符」而非「第i个字符」的语义是为了天然处理空串dp[0][j]表示空字符串与p前j个字符的匹配情况dp[i][0]表示s前i个字符与空模式串的匹配情况。由于p非空dp[i][0]只在i 0时为True其余情况均为False。3.3 状态转移方程从s的当前字符s[i-1]与p的当前字符p[j-1]的关系出发分三种情况讨论。情况 As[i-1] p[j-1]字符直接相等s的第i个字符与p的第j个字符匹配此时「前i与前j是否匹配」完全取决于「前i-1与前j-1是否匹配」$$ dp[i][j] dp[i-1][j-1] $$情况 Bp[j-1] .点号通配任意单字符.可以匹配任意单个字符因此当前字符必然匹配转移同上$$ dp[i][j] dp[i-1][j-1] $$情况 Cp[j-1] *星号重复前一元素这是本题的核心难点。*的作用对象是它前面的元素p[j-2]可以匹配0~ 若干次因此要再细分子情况 C1s[i-1] ! p[j-2]且p[j-2] ! .当前字符与*的前一元素既不相等、前一元素也不是.说明星号在此处一个字符也匹配不上只能选择匹配0次即匹配空字符串。此时相当于把p中的「p[j-2]*」这对组合整体丢弃问题退化为「s的前i个字符与p的前j-2个字符是否匹配」$$ dp[i][j] dp[i][j-2] $$子情况 C2s[i-1] p[j-2]或p[j-2] .说明*的前一元素p[j-2]可以匹配上s[i-1]此时有三种选择满足其一即可选择含义转移来源转移方程匹配0次丢弃p[j-2]*组合s前i个、p前j-2个dp[i][j-2]匹配1次用掉p[j-2]*不再重复s前i个、p前j-1个dp[i][j-1]匹配多次继续用p[j-2]匹配当前字符保留*处理s剩余字符s前i-1个、p前j个dp[i-1][j]综合起来$$ dp[i][j] dp[i][j-2] \ \text{or} \ dp[i][j-1] \ \text{or} \ dp[i-1][j] $$转移方程汇总$$dp[i][j] \begin{cases} dp[i-1][j-1] s[i-1] p[j-1] \text{ 或 } p[j-1] . \ dp[i][j-2] p[j-1] \text{ 且 } s[i-1] \ne p[j-2] \text{ 且 } p[j-2] \ne . \ dp[i][j-2] \ \text{or} \ dp[i][j-1] \ \text{or} \ dp[i-1][j] p[j-1] \text{ 且 } (s[i-1] p[j-2] \text{ 或 } p[j-2] .) \end{cases}$$3.4 初始条件dp[0][0] True两个空字符串是匹配的这是递推的基石。空字符串s与模式串p的匹配dp[0][j]当p[j-1] *时s为空意味着*只能匹配0次于是「空串与p前j个字符是否匹配」取决于「空串与p前j-2个字符是否匹配」$$ dp[0][j] dp[0][j-2] $$例如s 、p a*b*dp[0][0]Truej2时dp[0][2]dp[0][0]Truej4时dp[0][4]dp[0][2]True最终空串与a*b*匹配成功。而p a时dp[0][1]False空串无法匹配非空普通字符符合直觉。3.5 最终结果根据状态定义dp[i][j]表示s前i个字符与p前j个字符是否匹配则最终结果为dp[size_s][size_p]其中size_s是字符串s的长度size_p是字符串p的长度。它回答的正是「整个s与整个p是否完全匹配」。4. 思路 1动态规划代码实现以下是原题解中的完整 Python 实现我们补充了关键注释使其可直接复制运行class Solution: def isMatch(self, s: str, p: str) - bool: size_s, size_p len(s), len(p) # dp[i][j]: s 的前 i 个字符与 p 的前 j 个字符是否匹配 dp [[False for _ in range(size_p 1)] for _ in range(size_s 1)] # 初始条件两个空串匹配 dp[0][0] True # 初始条件空串 s 与 p 的匹配——只有 p[j-1] * 时 # 星号匹配 0 次才能让空串与 p 前 j 个字符匹配 for j in range(1, size_p 1): if p[j - 1] *: dp[0][j] dp[0][j - 2] # 递推填表 for i in range(1, size_s 1): for j in range(1, size_p 1): if s[i - 1] p[j - 1] or p[j - 1] .: # 情况 A / B当前字符直接匹配取决于各自前一前缀 dp[i][j] dp[i - 1][j - 1] elif p[j - 1] *: if s[i - 1] ! p[j - 2] and p[j - 2] ! .: # 情况 C1星号匹配不上只能匹配 0 次 dp[i][j] dp[i][j - 2] else: # 情况 C2匹配 0 次 / 1 次 / 多次三者满足其一即可 dp[i][j] dp[i][j - 1] or dp[i][j - 2] or dp[i - 1][j] # 最终结果整个 s 与整个 p 是否完全匹配 return dp[size_s][size_p]4.1 递推过程示例s aa、p a*状态计算过程结果dp[0][0]初始条件Truedp[0][2]p[1] *dp[0][2] dp[0][0]Truedp[1][1]s[0] p[0] adp[1][1] dp[0][0]Truedp[1][2]p[1] *且s[0] p[0] adp[1][2] dp[1][1] or dp[1][0] or dp[0][2]Truedp[2][1]s[1] p[0] adp[2][1] dp[1][0]Falsedp[2][2]p[1] *且s[1] p[0] adp[2][2] dp[2][1] or dp[2][0] or dp[1][2]True最终dp[2][2] Trueaa与a*匹配成功。其中dp[1][2]这一格贡献了关键一跳它表明「s的前 1 个字符a」与「p的前 2 个字符a*」匹配从而让dp[2][2]通过「匹配多次」的转移dp[i-1][j]得到True——这正是*让a重复两次的体现。4.2 复杂度分析时间复杂度$O(m n)$其中 $m$ 是字符串s的长度$n$ 是字符串p的长度。代码使用了两重循环外层循环遍历的时间复杂度是 $O(m)$内层循环遍历的时间复杂度是 $O(n)$每个状态的计算都是 $O(1)$ 的常数次布尔运算所以总体时间复杂度为 $O(m n)$。空间复杂度$O(m n)$。使用了一个 $(m1) \times (n1)$ 的二维数组保存全部状态其中第一维空间复杂度为 $O(m)$第二维为 $O(n)$因此总体空间复杂度为 $O(m n)$。5. 边界情况与易错点*匹配 0 次必须显式覆盖子情况 C1 中即使当前字符匹配不上dp[i][j]也不能直接置False而应回退到dp[i][j-2]。例如s ab、p c*abc*匹配 0 次后由ab完成匹配若忽略该分支会得到错误结果。空串初始化顺序dp[0][j]的填充依赖dp[0][j-2]必须从j1开始从左到右扫描p中非*的位置保持False不会被后续*错误地「激活」。.与*的组合.*表示「任意字符重复任意次」即可以匹配任意字符串包括空串。代码中子情况 C2 的判断条件p[j-2] .正是为此设计例如s ab、p .*应返回True。与 LeetCode 44 通配符匹配的语义差异「算法通关手册」中还有一道姊妹题 0044. 通配符匹配题解。两者形态相似但语义完全不同务必区分对比项0010 正则表达式匹配0044 通配符匹配通配字符.匹配任意单个字符?匹配任意单个字符星号语义*匹配零个或多个前面那一个元素作用于前一字符*匹配任意字符串含空串独立通配不依赖前一字符转移方程核心需分类讨论dp[i][j-2]、dp[i][j-1]、dp[i-1][j]三路dp[i-1][j] or dp[i][j-1]两路空串初始化dp[0][j] dp[0][j-2]依赖*前一元素模式串前缀连续为*时dp[0][j] True这道 44 题在面试 200 题列表 与分类题目列表 中与本题一起被归入「递归、字符串、动态规划」的困难题组建议对照练习以加深对两种星号语义的理解。6. 关联知识与阅读路径本题处于「算法通关手册」两条知识线的交汇处可按以下路径深入动态规划方法论先阅读 08_01 动态规划基础掌握「阶段划分 → 定义状态 → 状态转移 → 初始条件 → 最终结果」五步法这是本题推导所严格遵循的范式其核心的「表格处理方法」思想正是dp数组的来源。双串线性 DP 分类再阅读 08_04 双串线性 DP其中明确指出双串线性 DP 除最长公共子序列外还包括字符串模糊匹配问题并以编辑距离LeetCode 72为例展示了同构的状态设计。将本题与编辑距离对照可以提炼出「双指针推进 前缀关系」的通用套路。相关题解本题完整题解见 docs/solutions/0001-0099/regular-expression-matching.md姊妹题见 0044 通配符匹配题解同属双串 DP 的 0072 编辑距离题解 可作为进阶练习。题目索引本题同时收录于 题解总列表、分类列表递归 / 字符串 / 动态规划分类与面试 200 题列表属于算法面试的高频困难题值得反复咀嚼。7. 小结LeetCode 10 正则表达式匹配的核心难点在于*的三种匹配语义。通过二维布尔 DP用dp[i][j]精确表达「前缀是否匹配」这一子问题用「匹配 0 次 / 1 次 / 多次」三分支覆盖*的全部行为用dp[0][j] dp[0][j-2]处理好空串边界。最终以 $O(m n)$ 的时间复杂度和 $O(m n)$ 的空间复杂度完成求解。这既是双串线性 DP 的经典范式也是面试中考察「分类讨论 状态设计」能力的代表题目——透彻理解本题对后续攻克通配符匹配、编辑距离等同类题目将大有裨益。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Book 详解 LCR 137「模糊搜索验证」正则表达式匹配的动态规划解法LeetCode Book 详解 LCR 137「模糊搜索验证」正则表达式匹配的动态规划解法 导读 「模糊搜索验证」LeetCode LCR 137对应《示例工程Xcode-Dev-Cleaner释放数十GB存储空间的终极Xcode缓存清理工具Xcode Dev Cleaner释放数十GB存储空间的终极Xcode缓存清理工具 Xcode Dev Cleaner是一款专为开发者设计的高效Xcode缓存CS-Notes 剑指 Offer 19正则表达式匹配——用动态规划实现 . 与 * 匹配CS Notes 剑指 Offer 19正则表达式匹配——用动态规划实现 . 与 匹配 本篇基于 notes/19. 正则表达式匹配.md 展开讲解《剑指知识库文档教程上一篇解锁AI开发新境界一站式免费AI API资源库完全指南下一篇Windows 10系统PL2303串口驱动完美解决方案告别设备识别困扰创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考