LeetCode010——正则表达式匹配

标签: LeetCode  Java  递归  动态规划  正则表达式匹配

我的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代码:

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代码:

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];
	}
}

LeetCode解题报告: