题⽬描述

请实现⼀个函数⽤来匹配包括' . '和' * '的正则表达式。模式中的字符' . '表示任意⼀个字符，
⽽' * '表示它前⾯的字符可以出现任意次（包含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 的第⼀个字符去掉，两者接着匹配。
  • 否则，说明第⼆个字符不是 * ，那么就直接⽐较第⼀个字符是不是匹配，同时将后⾯的字符进⾏匹配。

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

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

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

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

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

public class Solution {
    private Boolean[][] memo; // 缓存数组：null未计算，true/false已计算
    
    public boolean isMatch(String s, String p) {
        memo = new Boolean[s.length() + 1][p.length() + 1];
        return dfs(0, 0, s, p);
    }
    
    private boolean dfs(int i, int j, String s, String p) {
        // 检查缓存是否存在当前子问题的解
        if (memo[i][j] != null) return memo[i][j];
        
        boolean result;
        // 模式串耗尽时，文本串也必须耗尽
        if (j == p.length()) {
            result = (i == s.length());
        } else {
            // 计算当前首字符匹配状态
            boolean firstMatch = (i 

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

动态规划（推荐）

动态规划：

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

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

public boolean match(String str, String pattern) {
	if (pattern.length() == 0) {
		return str.length() == 0;
	}
	
	int n = str.length() + 1;
	int m = pattern.length() + 1;
	boolean[][] dp = new boolean[n][m];
	dp[0][0] = true;
	
	for (int j = 2; j 

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

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

状态机优化：滚动数组降低空间复杂度，只保留当前行和上一行的状态，空间优化到O(n)

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 

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

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top