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 的第⼀个字符去掉，两者接着匹配。
  • 否则，说明第⼆个字符不是 * ，那么就直接⽐较第⼀个字符是不是匹配，同时将后⾯的字符进⾏匹配。

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

public boolean match(String str, String pattern) {
	if (pattern.length() == 0) {
		return str.length() == 0;
	}
	
	// 第⼆个字符是'*'
	if (pattern.length() > 1 && pattern.charAt(1) == '*') {
		// 匹配0次，直接把'*'去掉，两者判断
		- // 第⼀个字符相同的时候，去掉第⼀个字符，判断后⾯的（相当于匹配多次）
		return match(str, pattern.substring(2)) || (str.length() > 0 && firstSame(str, pattern)) && match(str.substring(1), pattern);
	} else {
	// 第⼆个字符不是 '*'的时候，判断第1个字符是否相同，相同的时候再从第2位开始⽐较
		return str.length() > 0 && firstSame(str, pattern) && (match(str.substring(1), pattern.substring(1)));
	}
}

// 判断第⼀个字符是不是相同
private boolean firstSame(String s, String p) {
	// 两个相同，或者有⼀个是"."
	return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.';
}

动态规划

上面这种做法不是最优的，使⽤了⼤量的递归操作，并且重复递归，时间复杂度⽐较⾼。

当然，这道题还有⼀个更优的做法，但是过程咋⼀看有点复杂，我们可以来分析⼀下，主要思路是动态规划：

1. ⾸先我们需要定义状态：⽤⼀个⼆维数组（套路） dp[i][j] ⽤来表示str 的前i 个字符和pattern 的前j 个字符是否匹配。
2. 接下来，我们需要初始化简单状态，因为想要求后⾯的状态，是依赖于前⾯的状态的，⼀般是初始化dp[i][j] 的⾸⾏和⾸列。
   • 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 < m; j = j + 2) {
		if (dp[0][j - 2] && pattern.charAt(j - 1) == '*') {
			dp[0][j] = true;
		}
	}
	
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (pattern.charAt(j - 1) == '*') {
			dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.');
			} else {
			dp[i][j] = dp[i - 1][j - 1] && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.');
			}
		}
	}
	return dp[n - 1][m - 1];
}

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