剑指offer-52、正则表达式匹配

题⽬描述

请实现⼀个函数⽤来匹配包括' . '和' * '的正则表达式。模式中的字符' . '表示任意⼀个字符，
⽽' * '表示它前⾯的字符可以出现任意次（包含0 次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串" aaa "与模式" a.a "和" ab*ac*a "匹配，但是与" aa.a "和" ab*a "均不匹
配
示例1
输⼊: "aaa","a*a"
返回值: true
示例2
输⼊："aad","c*a*d"
返回值：true
说明：因为这⾥ c 为 0 个，a被重复⼀次， * 表示零个或多个a。因此可以匹配字符串 "aad"。
示例3
输⼊："",".*"
返回值：true
说明：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）
思路及解答

递归

分类讨论，原串定义为str ,模式串为pattern 。`

• 如果pattern ⻓度为0
  
  
  
  • 且str ⻓度为0 ,说明刚刚好匹配完，返回ture
    
  • str ⻓度不为0 ，说明没有匹配完，返回false
    
  
  
• 如果pattern 的⻓度⼤于0
  
  
  
  • 如果pattern 的⻓度⼤于1 ，且第2 个字符是* ，说明前⾯的字符可以匹配0 ， 1 或者多次
    
    
    
    • 分为两种情况讨论：⼀种是直接把* 和* 前⾯的字符去掉，相当于匹配了0 个，然后接着⽐较；另外⼀种是，如果str 的⻓度⼤于0 ，并且第⼀个字符匹配，那就把str 的第⼀个字符去掉，两者接着匹配。
      
    
    
  • 否则，说明第⼆个字符不是 * ，那么就直接⽐较第⼀个字符是不是匹配，同时将后⾯的字符进⾏匹配。
    
  
  

注意：上⾯说的第⼀个字符是不是匹配，除了两个字符相等的情况，其实还有模式串的字符为' . '的情况。

1. public class Solution {
2.     public boolean isMatch(String s, String p) {
3.         // 模式串为空时，文本串也必须为空才匹配
4.         if (p.isEmpty()) return s.isEmpty();
5.         
6.         // 检查首字符匹配：文本串非空且字符相等或模式为'.'
7.         boolean firstMatch = !s.isEmpty() &&
8.                             (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
9.         
10.         // 处理'*'通配符（确保模式长度≥2且第二个字符是'*'）
11.         if (p.length() >= 2 && p.charAt(1) == '*') {
12.             // 两种情况：1) '*'匹配0个前驱字符 2) 匹配1个及以上前驱字符
13.             return isMatch(s, p.substring(2)) ||
14.                    (firstMatch && isMatch(s.substring(1), p));
15.         } else {
16.             // 无'*'情况：首字符匹配且剩余部分也匹配
17.             return firstMatch && isMatch(s.substring(1), p.substring(1));
18.         }
19.     }
20. }

复制代码

• 时间复杂度：最坏O((m+n)2^(m+n))
  
• 空间复杂度：O(m²+n²)递归栈
  

记忆化搜索（递归+缓存）

在递归基础上添加缓存，避免重复计算。使用二维数组存储s[i:]和p[j:]的匹配结果，避免重复递归

1. public class Solution {
2.     private Boolean[][] memo; // 缓存数组：null未计算，true/false已计算
3.    
4.     public boolean isMatch(String s, String p) {
5.         memo = new Boolean[s.length() + 1][p.length() + 1];
6.         return dfs(0, 0, s, p);
7.     }
8.    
9.     private boolean dfs(int i, int j, String s, String p) {
10.         // 检查缓存是否存在当前子问题的解
11.         if (memo[i][j] != null) return memo[i][j];
12.         
13.         boolean result;
14.         // 模式串耗尽时，文本串也必须耗尽
15.         if (j == p.length()) {
16.             result = (i == s.length());
17.         } else {
18.             // 计算当前首字符匹配状态
19.             boolean firstMatch = (i < s.length()) &&
20.                                 (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
21.             
22.             // 处理'*'通配符
23.             if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
24.                 result = dfs(i, j + 2, s, p) || // 匹配0次
25.                         (firstMatch && dfs(i + 1, j, s, p)); // 匹配1+次
26.             } else {
27.                 result = firstMatch && dfs(i + 1, j + 1, s, p);
28.             }
29.         }
30.         memo[i][j] = result; // 存储结果到缓存
31.         return result;
32.     }
33. }

复制代码

• 时间复杂度：O(m×n)
  
• 空间复杂度：O(m×n)
  

动态规划（推荐）

动态规划：

• ⾸先定义状态：⽤⼀个⼆维数组（套路） dp[j] ⽤来表示str 的前i 个字符和pattern 的前j 个字符是否匹配。
  
• 初始化简单状态
  
  
  
  • dp[0][0]= true ,表示两个空的字符串是匹配的。
    
  • dp 数组的⾸列，除了dp[0][0] 为true ，其他的都是false 。因为pattern 为空，但是s 不为空的时候，肯定不匹配。
    
  • dp 的⾸⾏，也就是str 为空的时候，如果pattern 的偶数位都是“*”,那么就可以匹配，因为可以选择匹配0 次。
    
  
  
• 初始化前⾯之后，后⾯的从索引1 开始匹配：
  
  
  • pattern 的第j 个字符为“ * ”(即是 pattern[j-1]=='*' )
    
    
    • 如果dp[j-2]==true ，那么dp[j]=true (相当于str的前i和pattern的前j-2个字符匹配，此时的* 前⾯的那个字符出现了0 次)。
      
    • 如果dp[i-1][j]==true 且str[i-1]==pattern[j-2] ，则dp[j] =true 。（如果str 的前i - 1 个字符和pattern 的前j 个字符匹配，并且str 的第i 个字符和pattern 的第j - 1 个字符相等,相当于‘ * ’前⾯的字符出现了1 次）
      
    • 如果dp[i-1][j]=true 且pattern[j-2]=='.' 的时候，则dp[j]=true 。(表示str 的前i-1 个和patten 的前j 个匹配，并且pattern 的第j-1 个是‘ . ’，第j 个是‘ * ’,那么说明可以匹配任何字符任何次数，⾃然str 可以多匹配⼀个字符。)
      
    
    
  • pattern 的第j 个字符不为“ * ”(即是pattern[j-1]！='*' )
    
    
    • 如果dp[i - 1][j - 1]=true and str[i - 1] == pattern[j - 1] 时，则dp[j]=true 。（也就是前⾯匹配，接下来的字符⼀样匹配）
      
    • 如果dp[i - 1][j - 1]=true 且pattern[i-1]=='.' ，那么dp[j]=true 。(其实也是. 可以匹配任何字符)
      
    
    
  
  

处理完数组之后，最后返回dp[n-1][m-1] ，也就是str 的前n 个和pattern 的前m 个字符是否匹配。

1. public boolean match(String str, String pattern) {
2.         if (pattern.length() == 0) {
3.                 return str.length() == 0;
4.         }
5.        
6.         int n = str.length() + 1;
7.         int m = pattern.length() + 1;
8.         boolean[][] dp = new boolean[n][m];
9.         dp[0][0] = true;
10.        
11.         for (int j = 2; j < m; j = j + 2) {
12.                 if (dp[0][j - 2] && pattern.charAt(j - 1) == '*') {
13.                         dp[0][j] = true;
14.                 }
15.         }
16.        
17.         for (int i = 1; i < n; i++) {
18.                 for (int j = 1; j < m; j++) {
19.                         if (pattern.charAt(j - 1) == '*') {
20.                         dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.');
21.                         } else {
22.                         dp[i][j] = dp[i - 1][j - 1] && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.');
23.                         }
24.                 }
25.         }
26.         return dp[n - 1][m - 1];
27. }

复制代码

• 时间复杂度 O(mn) ： 其中 m , n 分别为 str 和 pattern 的⻓度，状态转移需遍历整个 dp 矩阵。
  
• 空间复杂度 O(mn) ： 状态矩阵 dp 使⽤ O(mn) 的额外空间。
  

状态机优化（空间优化DP）

状态机优化：滚动数组降低空间复杂度，只保留当前行和上一行的状态，空间优化到O(n)
[code]public class Solution {    public boolean isMatch(String s, String p) {        int m = s.length(), n = p.length();        boolean[] dp = new boolean[n + 1];        boolean[] prev = new boolean[n + 1];                // 初始化第一行（空文本串情况）        dp[0] = true;        for (int j = 2; j