企业官网建设流程全解析

欢迎来到李耶的频道【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){constm=s.length;constn=p.length;constdp=Array.from({length:m+1},()=>Array(n+1).fill(false));// 空字符串和空模式匹配dp[0][0]=true;// 处理模式 p 的前缀为 'x*' 可以匹配空字符串的情况for(letj=1;j<=n;j++){if(p[j-1]==='*'&&dp[0][j-2]){dp[0][j]=true;}}for(leti=1;i<=m;i++){for(letj=1;j<=n;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){constmemo=newMap();functiondfs(i,j){// 模式已匹配完，检查字符串是否也匹配完if(j===p.length)returni===s.length;// 字符串已匹配完，检查剩余模式是否都是 "x*" 形式if(i===s.length){if((p.length-j)%2===1)returnfalse;for(letk=j+1;k<p.length;k+=2){if(p[k]!=='*')returnfalse;}returntrue;}constkey=i+','+j;if(memo.has(key))returnmemo.get(key);constfirstMatch=s[i]===p[j]||p[j]==='.';letresult=false;// 下一个字符是 '*'，处理两种情况if(j+1<p.length&&p[j+1]==='*'){// 情况1：'x*' 匹配 0 次，跳过// 情况2：'x*' 匹配 1 次以上result=dfs(i,j+2)||(firstMatch&&dfs(i+1,j));}else{// 无 '*'，常规匹配result=firstMatch&&dfs(i+1,j+1);}memo.set(key,result);returnresult;}returndfs(0,0);}

• 时间复杂度 / 空间复杂度：O(m·n) / O(m·n)
• 优势：思路直观，代码简洁，易于理解递归分支逻辑

解法对比

扩展题

1. 通配符匹配：给定一个字符串s和一个字符模式p，实现一个支持'?'和'*'的通配符匹配，其中'?'匹配任意单个字符，'*'匹配任意字符串。
2. 正则表达式匹配（支持更多语法）：在本题基础上，支持'+'（匹配 1 次或多次）、'?'（匹配 0 次或 1 次）等正则语法。
3. 字符串匹配算法：实现 KMP 或 BM 等经典的字符串匹配算法。

“千里之行，始于足下。” —— 老子

关注李耶，每天一道面试题，一起卷起来 🔥