欢迎来到李耶的频道【LeetCode面试题】。正则表达式匹配 10.正则表达式匹配题目给你一个字符串s和一个字符规律p请你来实现一个支持.和*的正则表达式匹配。.匹配任意单个字符*匹配零个或多个前面的那一个元素所谓匹配是要涵盖整个字符串s的而不是部分字符串。输入s aa, p a 输出false 解释a 无法匹配 aa 整个字符串。输入s aa, p a* 输出true 解释因为 * 代表可以匹配零个或多个前面的那一个元素在这里前面的元素就是 a。因此字符串 aa 可被视为 a 重复了一次。输入s ab, p .* 输出true 解释.* 表示可匹配零个或多个*任意字符.。输入s aab, p c*a*b 输出true 解释因为 * 表示零个或多个这里 c 为 0 个a 被重复一次。因此可以匹配字符串 aab。输入s mississippi, p mis*is*p*. 输出false解法一动态规划思路用dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。关键是处理*的两种情况匹配 0 次跳过x*或匹配 1 次以上继续使用x*。functionisMatch(s,p){constms.length;constnp.length;constdpArray.from({length:m1},()Array(n1).fill(false));// 空字符串和空模式匹配dp[0][0]true;// 处理模式 p 的前缀为 x* 可以匹配空字符串的情况for(letj1;jn;j){if(p[j-1]*dp[0][j-2]){dp[0][j]true;}}for(leti1;im;i){for(letj1;jn;j){// 当前字符匹配包括 . 通配符if(s[i-1]p[j-1]||p[j-1].){dp[i][j]dp[i-1][j-1];}elseif(p[j-1]*){// * 匹配 0 次前面的字符dp[i][j]dp[i][j-2];// 或者匹配 1 次以上当前字符与 * 前的字符匹配if(s[i-1]p[j-2]||p[j-2].){dp[i][j]dp[i][j]||dp[i-1][j];}}}}returndp[m][n];}时间复杂度 / 空间复杂度O(m·n) / O(m·n)其中 m、n 分别为 s 和 p 的长度优势逻辑清晰状态转移明确面试中最推荐的写法解法二递归带记忆化思路定义递归函数dfs(i, j)表示s[i:]与p[j:]是否匹配。遇到*时分支处理跳过x*或匹配当前字符后继续。用备忘录避免重复计算。functionisMatch(s,p){constmemonewMap();functiondfs(i,j){// 模式已匹配完检查字符串是否也匹配完if(jp.length)returnis.length;// 字符串已匹配完检查剩余模式是否都是 x* 形式if(is.length){if((p.length-j)%21)returnfalse;for(letkj1;kp.length;k2){if(p[k]!*)returnfalse;}returntrue;}constkeyi,j;if(memo.has(key))returnmemo.get(key);constfirstMatchs[i]p[j]||p[j].;letresultfalse;// 下一个字符是 *处理两种情况if(j1p.lengthp[j1]*){// 情况1x* 匹配 0 次跳过// 情况2x* 匹配 1 次以上resultdfs(i,j2)||(firstMatchdfs(i1,j));}else{// 无 *常规匹配resultfirstMatchdfs(i1,j1);}memo.set(key,result);returnresult;}returndfs(0,0);}时间复杂度 / 空间复杂度O(m·n) / O(m·n)优势思路直观代码简洁易于理解递归分支逻辑解法对比解法时间 / 空间复杂度优势推荐指数动态规划O(m·n) / O(m·n)状态转移清晰面试优选⭐⭐⭐⭐⭐递归记忆化O(m·n) / O(m·n)代码简洁逻辑直观⭐⭐⭐⭐扩展题通配符匹配给定一个字符串s和一个字符模式p实现一个支持?和*的通配符匹配其中?匹配任意单个字符*匹配任意字符串。正则表达式匹配支持更多语法在本题基础上支持匹配 1 次或多次、?匹配 0 次或 1 次等正则语法。字符串匹配算法实现 KMP 或 BM 等经典的字符串匹配算法。“千里之行始于足下。” —— 老子关注李耶每天一道面试题一起卷起来