CS-Notes 剑指 Offer 19正则表达式匹配——用动态规划实现.与*匹配【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 notes/19. 正则表达式匹配.md 展开讲解《剑指 Offer》第 19 题“正则表达式匹配”的完整动态规划解法如何为.任意字符与*前导字符重复 0 次或多次定义状态、推导状态转移方程、处理首行边界初始化并逐行读懂仓库中的 Java 参考实现。读完后你可以独立写出这道题的 O(mn) 解法并理解每一行转移对应的匹配语义。一、题目描述与匹配语义实现一个函数用来匹配包括.和*的正则表达式规则如下模式中的字符.表示任意一个字符*表示它前面的字符可以出现任意次包含 0 次。“匹配”是指字符串的所有字符匹配整个模式full match而非搜索子串。题目给出的判定示例字符串模式是否匹配aaaa.a匹配aaaab*ac*a匹配aaaaa.a不匹配aaaab*a不匹配这里要先厘清元字符语义仓库中 notes/正则表达式.md 对正则语法有系统梳理其中与本題直接相关的两点.是元字符匹配任何单个字符绝大多数实现中不匹配换行符若需匹配字面量的.需转义*是重复匹配元字符表示前面元素匹配0 个或多个。注意本题的*语义是“前导字符重复任意次”这与完整正则引擎中*只作用于紧邻的前一个元素的行为一致但与{m,n}、等其他量词无关——本题只需处理.和*两种元字符。二、解题思路先避开一个常见误区原文明确提示了一个关键认知点见 notes/19. 正则表达式匹配.md 解题思路一节应该注意到.是用来当做一个任意字符而*是用来重复前面的字符。这两个的作用不同不能把.的作用和*进行类比从而把它当成重复前面字符一次。也就是说*与.没有任何组合关系a*是“a 重复 0 次或多次”不存在.*之外的隐式规则。想清楚这一点后问题就可以抽象成标准的双序列动态规划给定字符串str长度 m与模式pattern长度 n判断str的前 i 个字符能否被pattern的前 j 个字符完整匹配。三、状态定义与状态转移设dp[i][j]表示字符串的前i个字符与模式的前j个字符是否匹配。数组规模为(m1) x (n1)dp[m][n]即为答案。逐字符比较时按模式第j个字符下标j-1分两类情况 1pattern[j-1]不是*只有当它与str[i-1]相等、或它是.时才能各消耗一个字符if (str.charAt(i - 1) pattern.charAt(j - 1) || pattern.charAt(j - 1) .) dp[i][j] dp[i - 1][j - 1];情况 2pattern[j-1]是*此时需考察*前面的字符pattern[j-2]与当前字符str[i-1]是否“相等”相等或为.。相等时*有三种解释对应三条转移dp[i][j] | dp[i][j - 1]; // a* counts as single ax* 消耗 1 个 x dp[i][j] | dp[i - 1][j]; // a* counts as multiple ax* 消耗多个 x dp[i][j] | dp[i][j - 2]; // a* counts as emptyx* 整体不出现不等时x*只能整体不出现出现 0 次转移退化为dp[i][j] dp[i][j - 2]; // a* only counts as empty这三条转移覆盖了*的全部语义dp[i][j-1]对应“重复恰好到当前字符为止”可重复推导出 1 次的情形dp[i-1][j]对应“已重复多次再来一个”dp[i][j-2]对应“重复 0 次、跳过x*两个模式字符”。四、完整 Java 实现与逐行解读仓库给出的完整实现如下摘自 notes/19. 正则表达式匹配.md可直接复制运行public boolean match(String str, String pattern) { int m str.length(), n pattern.length(); boolean[][] dp new boolean[m 1][n 1]; dp[0][0] true; for (int i 1; i n; i) if (pattern.charAt(i - 1) *) dp[0][i] dp[0][i - 2]; for (int i 1; i m; i) for (int j 1; j n; j) if (str.charAt(i - 1) pattern.charAt(j - 1) || pattern.charAt(j - 1) .) dp[i][j] dp[i - 1][j - 1]; else if (pattern.charAt(j - 1) *) if (pattern.charAt(j - 2) str.charAt(i - 1) || pattern.charAt(j - 2) .) { dp[i][j] | dp[i][j - 1]; // a* counts as single a dp[i][j] | dp[i - 1][j]; // a* counts as multiple a dp[i][j] | dp[i][j - 2]; // a* counts as empty } else dp[i][j] dp[i][j - 2]; // a* only counts as empty return dp[m][n]; }逐段说明dp[0][0] true空字符串与空模式匹配是整个递推的根。首行初始化字符串为空、模式非空只有形如a*的连续模式才可能匹配空串。pattern.charAt(i-1) *时执行dp[0][i] dp[0][i-2]即“x*不出现”地向前递推遇到非*字符则保持false。这保证了例如模式a*b*c*能正确判定与空串的匹配。注意该写法依赖*前面必有字符与题目“*表示它前面的字符”的约定一致。主循环按上文两种情况填表时间复杂度 O(mn)空间复杂度 O(mn)——由代码中(m1) x (n1)的二维布尔表可直接确认由于dp[i][j]只依赖上一行与同行左侧状态空间可压缩到 O(n)但这属于进一步优化原实现优先保证可读性。|的使用三条转移取“或”只要任一种解释成立即匹配成功这正是*多义性的体现。五、例子走查以题目示例str aaa,pattern ab*ac*a走一遍关键格子的推导验证转移正确性dp[0][3]模式前 3 位是ab*b*可取 0 次故dp[0][3] dp[0][1]为true空前缀a无法匹配空串但递推链条dp[0][3]dp[0][1]为false此处真正起作用的是下面带字符的格子。匹配第 1 个adp[1][1] dp[0][0] true直接字符相等。处理b*对b*b与当前字符a不等走dp[i][j] dp[i][j-2]即b*取 0 次状态平移到跳过b*。处理c*同理取 0 次末尾a与最后一个a相等dp[3][7] dp[2][6]最终dp[3][7] true匹配成功。而pattern ab*a匹配aaa失败的原因也能从表格中看出b*取 0 次后模式只剩一个a去匹配字符串末尾中间多出的字符无处消耗dp[3][4]最终为false。另外注意首行初始化中的一个隐含约束若模式以*开头如*a上面的dp[0][i] dp[0][i-2]会访问下标 -1。本题约定*前面必有字符输入模式合法因此参考实现未做防御性检查若用于更通用的输入需要自行约定这类模式的语义。六、适用前提与边界约定本题的“匹配”是全串匹配与String.matches语义一致不同于正则搜索search只要求部分匹配元字符仅两种.与*不涉及、?、[]、分组等语法后者的系统讲解可参考 notes/正则表达式.md 中“重复匹配”“匹配一组字符”等小节实现假设模式合法*前有字符且字符比较按 Javachar精确相等判断该题在仓库的 剑指 Offer 题解 - 目录 中归入“其它”分类但它本质是字符串双序列 DP与同目录下 10.1 斐波那契数列 等动态规划题目共享“状态定义 转移方程”的解题框架可与 42. 连续子数组的最大和、48. 最长不含重复字符的子字符串 对照练习 DP 的建模思路。七、小结状态定义dp[i][j]str前i字符能否被pattern前j字符匹配非*字符逐字符比对.等价于“任意字符”*字符前导字符能匹配当前字符时走三条转移1 次 / 多次 / 0 次否则只能整体跳过0 次首行按dp[0][i] dp[0][i-2]初始化覆盖“x*全取 0 次”的合法空匹配时间 O(mn)、空间 O(mn)代码完整可复制自 notes/19. 正则表达式匹配.md。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考