LeetCode010——正则表达式匹配

150 阅读 0 评论 99 点赞

我是靠谱客的博主尊敬路灯，这篇文章主要介绍LeetCode010——正则表达式匹配，现在分享给大家，希望可以做个参考。

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/regular-expression-matching/description/

题目描述：

知识点：递归、动态规划

思路一：递归

递归的终止条件：

（1）如果s字符串的长度为0，如果此时字符串p当且仅当有形如"a*b*c*d*e*"这样的格式时，返回true；否则，返回false。

（2）如果s字符串的长度不为0，而p字符串的长度为0，返回false。

递归的过程：

（1）如果s的最后一个字符与p的最后一个字符相等，或者说p的最后一个字符为"."，那么我们直接看字符串s中除去最后一个字符的字符串能否与字符串p中除去最后一个字符的字符串相匹配。

（2）如果p的最后一个字符为"*"，这种情况比较复杂，又分为两种情况。

a.如果s的最后一个字符既不与p的最后第二个字符相等，p的最后第二个字符也不为"."，那么我们直接看字符串s能否与字符串p中除去最后两个字符的字符串相匹配。

b.如果s的最后一个字符与p的最后第二个字符相等，或者说p的最后第二个字符为"."，，这种情况比较复杂，又分为三种情况。

b-1：我们看字符串s中除去最后一个字符的字符串能否与字符串p相匹配（即把s中的最后一个字符与p的最后一个字符（*）相匹配）。

b-2：我们看字符串s能否与字符串p中除去最后一个字符的字符串相匹配（即把s中的最后一个字符与p的最后第二个字符相匹配）。

b-3：我们看字符串s中除去最后一个字符的字符串能否与字符串p中除去最后两个字符的字符串相匹配（直接舍去p中的最后两个字符）。

只要上述b-1、b-2、b-3三种情况中有一种情况相匹配，我们就返回true。如果三种情况都不匹配，我们就返回false。

每一次递归的时间复杂度是O(1)级别的，我们最多需要递归m * n次，其中m为字符串s的长度，n为字符串p的长度，时间复杂度是O(m * n)。由于递归存在对系统栈的调用，因此空间复杂度与递归深度成正比，而递归的最大深度是m * n，因此空间复杂度是O(m * n)。

JAVA代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {

	public boolean isMatch(String s, String p) {
		int ns = s.length();
		int np = p.length();
		if(ns != 0 && np == 0) {
			return false;
		}
		if(ns == 0) {
			if(np % 2 == 1) {
				return false;
			}
			int i = 1;
	        while (i < p.length() && p.charAt(i) == '*') {
	        	i += 2;
	        }
	        if(i == p.length() + 1) { 
	        	return true;
	        }else {
	        	return false;
	        }
		}
		if(s.charAt(ns - 1) == p.charAt(np - 1) || p.charAt(np - 1) == '.') {
			return isMatch(s.substring(0, ns - 1), p.substring(0, np - 1));
		}
		if(p.charAt(np - 1) == '*') {
			if(s.charAt(ns - 1) != p.charAt(np - 2) && p.charAt(np - 2) != '.') {
				return isMatch(s.substring(0, ns), p.substring(0, np - 2));
			}else {
				return isMatch(s.substring(0, ns - 1), p) || isMatch(s.substring(0, ns), p.substring(0, np - 1)) || isMatch(s.substring(0, ns), p.substring(0, np - 2));
			}
		}
		return false;
	}
}

LeetCode解题报告：

思路二：动态规划

用题给的示例4来模拟递归的过程如下图所示：

图中紫色椭圆所在区域就是递归过程中出现的重叠子问题，既然发现了重叠子问题，那么肯定就可以用动态规划来解决！而动态规划的关键是状态定义的合适选取以及发现正确的状态转移。

状态定义：

f(x, y)------字符串s中[0, x - 1]范围内的字符串能否匹配字符串p中[0, y - 1]范围内的字符串

状态转移：

（1）如果p(y) == '.', f(x, y) = f(x - 1, y - 1)。

（2）如果p(y) == s(x), f(x, y) = f(x - 1, y - 1)。
（3）如果p(y) == '*'，
a.如果s(x) == p(y - 1) || p(y - 1) == '.'，
a-1：使用'*'号进行匹配——f(x - 1, y)
a-2：只使用'*'号前面的那个字符匹配，不使用'*'匹配——f(x, y - 1)
a-3：'*'号前面的那个字符在匹配的过程当中一个都不使用——f(x, y - 2)
f(x, y) = f(x - 1, y) || f(x, y - 1) || f(x, y - 2)。
b.如果s(x) != p(y - 1) && p(y - 1) != '.'
*号前面的那个字符在匹配的过程当中一个都不使用，f(x, y) = f(x, y - 2)。

为了处理s为空的情形，我们定义状态转移数组matched的行数和列数分别为s.length() + 1和p.length() + 1。显然我们有matched[0][0] = true。对于第0行，相当于字符串s为空，就是思路一中递归的终止条件（1）中的情形。

此思路的时间复杂度是O(m * n)，其中m为字符串s的长度，n为字符串p的长度，但相比思路一省略了很多重叠子问题的重复计算。空间复杂度是一个boolean类型的m * n的数组，因此空间复杂度是O(m * n)。

JAVA代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {

	public boolean isMatch(String s, String p) {
		int ns = s.length() + 1;
		int np = p.length() + 1;
		boolean[][] matched = new boolean[ns][np];
		//当s字符串为空的特殊处理

		//f(0, 0)表示s字符串为空，p字符串为空的情形
		matched[0][0] = true;
		//状态转移过程
		for (int i = 0; i < ns; i++) {
			for (int j = 1; j < np; j++) {
				if(i > 0 && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1))) {
					matched[i][j] = matched[i - 1][j - 1];
				}
				if(p.charAt(j - 1) == '*') {
					if(i == 0 || (s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.')) {
						matched[i][j] = matched[i][j - 2];
					}else {
						matched[i][j] = matched[i - 1][j] || matched[i][j - 1] || matched[i][j - 2];
					}
				}
			}
		}
		return matched[ns - 1][np - 1];
	}
}