【笔面试算法学习专栏】正则表达式匹配：10.正则表达式匹配

学习目标理解正则表达式匹配问题的定义掌握动态规划解决正则匹配问题的方法理解状态机思想在正则匹配中的应用区分.和*的特殊含义能够手写出完整的正则匹配代码理解时间复杂度的优化思路一、引言正则表达式匹配问题1.1 问题描述正则表达式匹配是LeetCode第10题也是一道经典的困难级别面试题。问题定义给定一个字符串s包含字母和数字和一个字符p包含字母、数字、.和*实现一个函数来匹配完整的字符串。特殊字符的含义.匹配任意单个字符*匹配零个或多个前面的那一个元素匹配规则如果是普通字符则必须精确匹配.可以匹配任意单个字符*必须与它前面的字符配合使用表示零个或多个该字符示例输入: s aa, p a 输出: false 解释: a 无法匹配 aa 输入: s aa, p a* 输出: true 解释: * 表示零个或多个 a所以匹配两个 a 输入: s ab, p .* 输出: true 解释: .* 表示零个或多个任意字符匹配任意字符串1.2 问题难点分析这个问题的难点在于*的含义取决于它前面的字符组合起来有三种含义零个该字符如a*可以匹配空字符串一个该字符aa可以匹配a*多个该字符aaa也可以匹配a*.可以匹配任意字符增加了灵活性需要考虑所有可能的组合情况二、解题思路2.1 暴力搜索递归最直观的想法是枚举所有可能的匹配方式。对于每个*我们都需要尝试匹配0个字符匹配1个字符匹配2个字符…defisMatch_brutal(s:str,p:str)-bool: 暴力递归解法会超时 时间复杂度: O(2^n) 空间复杂度: O(n) 递归栈深度 ifnotp:returnnots first_matchlen(s)0and(p[0]s[0]orp[0].)iflen(p)2andp[1]*:# 两种选择跳过 p[0]*或者消耗一个 s[0]return(first_matchandisMatch_brutal(s[1:],p))orisMatch_brutal(s,p[2:])else:returnfirst_matchandisMatch_brutal(s[1:],p[1:])暴力解法的问题在于当字符串和模式串都很长时会有指数级的递归调用导致超时。2.2 动态规划自底向上重叠子问题在暴力递归中我们会多次计算相同的子问题如s[1:]和p。动态规划通过保存这些子问题的结果来避免重复计算。状态定义dp[i][j] True 如果 s[i:] 能被 p[j:] 匹配 False otherwise状态转移普通字符或.dp[i][j] dp[i1][j1] 如果 s[i] 与 p[j] 匹配*的情况这是最难处理的部分p[j1] * 时有两种选择 a) 匹配0个 p[j]dp[i][j] dp[i][j2] b) 匹配1个或多个 p[j]前提是 s[i] 能匹配 p[j] dp[i][j] dp[i1][j] 如果 s[i] 匹配 p[j]三、动态规划详细推导3.1 状态转移图解让我们通过具体例子来理解状态转移示例s aab,p c*a*b模式串 p: c * a * b 索引 j: 0 1 2 3 4dp表行表示s的位置列表示p的位置“”c*a*b“”✓✗✓✗✓✓a✗✗✗✓✓✗a✗✗✗✗✓✗b✗✗✗✗✗✓3.2 代码实现defisMatch(s:str,p:str)-bool: 动态规划解法 dp[i][j]: s[i:] 能否被 p[j:] 匹配 时间复杂度: O(n*m) 空间复杂度: O(n*m) n,mlen(s),len(p)# dp[i][j] True 表示 s[i:] 能被 p[j:] 匹配dp[[False]*(m1)for_inrange(n1)]# base case: 空字符串和空模式串匹配dp[n][m]True# 边界空字符串能否被模式串匹配forjinrange(m-1):ifp[j]!*:breakdp[n][j2]dp[n][j]# 关键# 填充 dp 表从后往前foriinrange(n-1,-1,-1):forjinrange(m-1,-1,-1):first_match(s[i]p[j]orp[j].)ifj1mandp[j1]*:# * 的情况选择0个 或 继续匹配1个# 1. 选择0个跳过 c* 这部分dp[i][j]dp[i][j2]# 2. 选择1个或多个前提是 first_matchiffirst_match:dp[i][j]dp[i][j]ordp[i1][j]else:# 普通情况必须当前字符匹配dp[i][j]first_matchanddp[i1][j1]returndp[0][0]3.3 状态转移详解情况1p[j] 是普通字符或.dp[i][j] first_match and dp[i1][j1] 解释 - first_match: 当前字符必须匹配相等 或 p[j] . - dp[i1][j1]: 剩余部分继续匹配情况2p[j1] ‘*’这是最复杂的情况有两种选择选择A匹配0个 p[j]dp[i][j] dp[i][j2]例如s b,p a*b虽然a*可以匹配多个a但这里选择匹配0个a直接跳过a*用b去匹配b选择B匹配1个或多个 p[j]dp[i][j] dp[i1][j] 如果 first_match例如s aa,p a*第一个a匹配成功消耗s[0]a*继续尝试匹配剩余的a递归直到所有a都被消耗四、空间优化4.1 一维数组优化观察到 dp 表的递推只依赖dp[i1][j]和dp[i1][j1]当前行的下一行因此可以将二维数组压缩为一维。defisMatch_optimized(s:str,p:str)-bool: 空间优化的动态规划 时间复杂度: O(n*m) 空间复杂度: O(m) n,mlen(s),len(p)# dp[j] 表示 s[i:] 能否被 p[j:] 匹配dp[False]*(m1)dp[m]True# 从后往前遍历 sforiinrange(n,-1,-1):# 从后往前遍历 pforjinrange(m-1,-1,-1):first_matchinand(s[i]p[j]orp[j].)ifj1mandp[j1]*:dp[j]dp[j2]# 选择0个iffirst_match:dp[j]dp[j]ordp[j]# 选择1个或多个需要保存上一行的值else:dp[j]first_matchanddp[j1]returndp[0]优化版本正确实现defisMatch_optimized(s:str,p:str)-bool: 空间优化的动态规划正确版本 n,mlen(s),len(p)# 初始化dp[j] s[i:] 能否被 p[j:] 匹配dp[False]*(m1)dp[m]True# 从 s 的末尾向前遍历foriinrange(n-1,-1,-1):new_dp[False]*(m1)forjinrange(m-1,-1,-1):first_match(s[i]p[j]orp[j].)ifj1mandp[j1]*:# 选择0个 或 选择1个/多个new_dp[j]new_dp[j2]# 匹配0个iffirst_match:new_dp[j]new_dp[j]ordp[j]# 匹配1个或多个else:new_dp[j]first_matchanddp[j1]dpnew_dpreturndp[0]五、状态机视角5.1 从正则表达式到状态机正则表达式本质上定义了一个有限状态自动机FSA。每个字符包括.和*对应状态机中的一条或多条转移。状态机的表示状态表示当前位置模式串的索引转移根据当前字符和模式串字符决定下一状态.的转移状态 i --(任意字符)-- 状态 i1*的转移状态 i --(匹配0个)-- 状态 i2 状态 i --(匹配1个匹配字符)-- 状态 i 状态 i --(匹配2个匹配字符)-- 状态 i ...5.2 状态机代码实现fromfunctoolsimportlru_cachedefisMatch_state_machine(s:str,p:str)-bool: 状态机/记忆化搜索解法 n,mlen(s),len(p)lru_cache(maxsizeNone)defdp(i:int,j:int)-bool: 判断 s[i:] 能否被 p[j:] 匹配 ifjm:returnin first_matchinand(s[i]p[j]orp[j].)ifj1mandp[j1]*:# 两种选择跳过 *或者消耗一个字符returndp(i,j2)or(first_matchanddp(i1,j))else:returnfirst_matchanddp(i1,j1)returndp(0,0)六、LeetCode真题详解6.1 完整解题代码classSolution:defisMatch(self,s:str,p:str)-bool: 方法一动态规划 dp[i][j] s[i:] 能否被 p[j:] 匹配 时间复杂度: O(n*m) 空间复杂度: O(n*m) n,mlen(s),len(p)dp[[False]*(m1)for_inrange(n1)]dp[n][m]True# 处理空字符串与模式串的匹配forjinrange(m-1,-1,-1):ifp[j]!*:breakdp[n][j]Falsedp[n][j1]dp[n][j1-2ifj2elsej1]foriinrange(n-1,-1,-1):forjinrange(m-1,-1,-1):first_matchs[i]p[j]orp[j].ifj1mandp[j1]*:# * 的两种情况dp[i][j]dp[i][j2]# 匹配0个iffirst_match:dp[i][j]dp[i][j]ordp[i1][j]# 匹配1个或多个else:dp[i][j]first_matchanddp[i1][j1]returndp[0][0]defisMatch_memo(self,s:str,p:str)-bool: 方法二记忆化搜索更易理解 fromfunctoolsimportlru_cache n,mlen(s),len(p)lru_cache(maxsizeNone)defdfs(i:int,j:int)-bool:ifjm:returnin firstinand(s[i]p[j]orp[j].)ifj1mandp[j1]*:# 跳过 c* 或 消耗一个字符returndfs(i,j2)or(firstanddfs(i1,j))else:returnfirstanddfs(i1,j1)returndfs(0,0)6.2 测试用例deftest():solutionSolution()test_cases[(aa,a,False),(aa,a*,True),(ab,.*,True),(aab,c*a*b,True),(mississippi,mis*is*p*.,False),(,,True),(,a*,True),(,a*b*c*,True),(a,.*..,False),(ab,.*c,False),]fors,p,expectedintest_cases:resultsolution.isMatch(s,p)status✓ifresultexpectedelse✗print(f{status}isMatch({s!r},{p!r}) {result}, expected{expected})test()七、复杂度分析7.1 时间复杂度暴力递归O(2^(nm))每个位置都有两种选择匹配或不匹配最坏情况下指数级动态规划O(n*m)填满一个 n×m 的表格每个单元格只计算一次记忆化搜索O(n*m)同样的状态空间每个状态只计算一次7.2 空间复杂度二维DPO(n*m)需要保存整个 dp 表一维DPO(m)只保存当前行记忆化搜索O(nm)递归栈深度 缓存大小八、变形题与扩展8.1 通配符匹配LeetCode 44与正则匹配类似但通配符的语义不同?匹配任意单个字符*匹配任意序列包括空序列关键区别正则的*必须与前一个字符配合通配符的*可以独立使用8.2 重复的字符串匹配LeetCode 686给定字符串 A 和 B问 A 重复多少次可以包含 B解法将 A 重复 2 次加长然后使用正则或 KMP 匹配defrepeatedStringMatch(A:str,B:str)-int:ifBinA:return1n1repeatedAwhilelen(repeated)len(B):repeatedA n1ifBinrepeated:returnn repeatedAreturnn1ifBinrepeatedelse-18.3 正则表达式匹配扩展版本考虑加入更多正则特性匹配一个或多个前一个字符{n}精确匹配 n 个{n,m}匹配 n 到 m 个defisMatch_extended(s:str,p:str)-bool: 扩展版本支持 , {n}, {n,m} importre# 转换为标准正则pp.replace(,*)# 转为 * (但会改变语义这里简化处理)returnbool(re.fullmatch(p,s))九、面试要点总结9.1 核心思路识别问题本质字符串匹配 正则语法选择正确方法动态规划是标准解法理解状态转移特别是*的两种情况9.2 回答话术问题如何用动态规划解决正则表达式匹配参考答案我会定义dp[i][j]表示s[i:]能否被p[j:]匹配。对于普通字符和.状态转移很简单当前字符匹配且剩余部分匹配即可。关键在于*的处理。当p[j1] *时有两种选择匹配0个跳过x*这部分dp[i][j] dp[i][j2]匹配1个或多个前提是s[i]能匹配p[j]dp[i][j] dp[i1][j]最终答案是dp[0][0]。9.3 代码模板defisMatch(s:str,p:str)-bool:n,mlen(s),len(p)dp[[False]*(m1)for_inrange(n1)]dp[n][m]Trueforiinrange(n-1,-1,-1):forjinrange(m-1,-1,-1):firsts[i]p[j]orp[j].ifj1mandp[j1]*:dp[i][j]dp[i][j2]iffirst:dp[i][j]dp[i][j]ordp[i1][j]else:dp[i][j]firstanddp[i1][j1]returndp[0][0]十、总结正则表达式匹配是考察动态规划能力的经典题目。核心要点状态定义dp[i][j]表示子问题的解状态转移普通字符精确匹配.任意字符匹配*匹配0个或多个关键难点base case空字符串与空模式串复杂度O(n×m) 时间O(n×m) 空间可优化学习建议先理解递归版本再转换为迭代版本重点理解*的两种选择手动模拟几个例子加深理解推荐阅读LeetCode 10. 正则表达式匹配 - 官方题解《算法导论》第32章字符串匹配有限状态自动机理论