题目: 正则表达式匹配

来自智得网
跳转至： 导航、​ 搜索

分析

如果给定两个字符串进行比较是否相等，很容易想到逐个比较两个字符串中的字符来判断字符串是否相等，用两个指针分别指向两个数组的头部，之后两个指针每次向后移动一个字符，移动过程中判断指针指向的两个字符是否相等，如果直到指针移动到字符串尾部字符都相等，则可以判定两个字符串相等。

引入*和.之后情况会变得复杂，因为*可以匹配0个或多个字符，所以在匹配过程，采用双指针的方式不知道本次需要匹配多少字符，一旦匹配字符数目错误，还涉及到字符串的回退等操作。

涉及到回退操作，双指针求解的方式不能使用一个变量例如字符串s的位置来求解，至少需要s的位置以及p的位置等两个变量。

观察字符串以及正则表达式，可以发现该问题是一个重叠子结构的问题，比如 s[0..i] 和 p[0..j] 如果匹配，p[j] 如果是普通的字符串，那么 s[0..i-1] 和 p[0..j-1] 一定也是匹配的，如果 p[j] 的字符是 * ，那么一定可以在s中找到一个位置 n 使得 s[0..n] 和 p[0..j-2] 匹配。

而且该子结构的求解无后效行，因此可以尝试采用动态规划法解决该问题。

动态规划

动态规划一般分为确定变量，确定状态转移方程，确定边界条件等三个步骤。

该题目需要两个变量，分别是s、p当前字符的位置。

假设当前 s 、 p 的位置分别是 i 和 j ,正则表达式的方程可以定位为 dp[i][j] , dp[i][j]的值为true或者false，分别表示匹配或者不匹配两种情况。

因为题目需要判断正则表达式是否匹配，所以一旦不匹配则直接返回，假设当前 s 、 p 的位置分别是 i 和 j ，前序的字符串和正则表达式是匹配的，即 s[0..i-1] 和 p[0..j-1] 匹配，现在需要判断何等条件才能使得 s[0..i] 是否可以匹配p。

正则表达式匹配

根据 p[j-1] 的值分两种情况分析：

如果 p[j-1] 不等于 * ,同时 dp[i-1][j-1] = true ，

则说明当前的匹配不是使用 .* 或者 [a-z]* 等模式进行匹配的，后续字符的匹配字符串s和正则表达式都需要往后移，同时要求p的下一个字符要么和s的下一个字符相等，要么p的下一个字符是“.”从而可以匹配任何字符。

即。

如果 p[j-1] 等于 *，同时 dp[i-1][j-1] = true，

可以分为三种情况：

第一种情况是.*或者[a-z]* 匹配0个字符的情况，可以推出dp[i][j]=dp[j][j-2]。

第二种情况是.*或者[a-z]* 匹配一个字符的情况，此时可以推导(p[j - 2] == '.' || p[j - 2] == s[i - 1])，而且dp[i-1][j-2]也要同时为true。

第三种情况是.*或者[a-z]* 匹配多于一个字符的情况，此时可以推导(p[j - 2] == '.' || p[j - 2] == s[i - 1])，而且dp[i-1][j]也要同时为true。

所以最总的状态转移方式是：

动态规划的边界则直接比较第一个字符即可和正则表达式是否相等或者正则表达式第一个字符是否为.即可。

该题目的时间复杂为O（m*n）。

题解

func Solute(s string, p string) bool {
	if p[0] == '*' {
		return false
	}

	dp := make([][]bool, len(s)+1)
	for i := 0; i < len(s)+1; i++ {
		dp[i] = make([]bool, len(p)+1)
	}
	dp[0][0] = true
	for i := 1; i <= len(p); i++ {
		if p[i-1] == '*' {
			dp[0][i] = dp[0][i-2]
		}
	}

	for i := 1; i <= len(s); i++ {
		for j := 1; j <= len(p); j++ {
			if p[j-1] != '*' {
				dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1]
			} else if p[j-1] == '*' {
				dp[i][j] = dp[i][j - 2] || 
					((p[j - 2] == '.' || p[j - 2] == s[i - 1]) && (dp[i - 1][j - 2] || dp[i - 1][j]))
			}
		}
	}
	return dp[len(s)][len(p)]
}
取自“https://www.aigetting.com/index.php?title=题目:正则表达式匹配&oldid=2087”