KK's blog

每天积累多一些

0%

LeetCode 010 Regular Expression Matching

Posted on Edited on Disqus:

LeetCode 010 Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

<pre>'.' Matches any single character. '*' Matches zero or more of the preceding element. </pre>

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

<pre>Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". </pre>

Example 2:

<pre>Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". </pre>

Example 3:

<pre>Input: s = "ab" p = "." Output: true Explanation: "." means "zero or more (*) of any character (.)". </pre>

Example 4:

<pre>Input: s = "aab" p = "cab" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab". </pre>

Example 5:

<pre>Input: s = "mississippi" p = "misisp*." Output: false </pre>

题目大意：

这道求正则表达式匹配的题和那道Leetocde 044 Wildcard Matching很类似，不同点在于*的意义不同，在之前那道题中，
*表示可以代替任意个数的不同字符，而这道题中的*表示之前一个字符（同样字符）可以有0-N个匹配。此题更难一些。

解题思路：

这是经典题。两字符串匹配题基本就是DP而且知道子问题答案可以推导下一个。

  1. 定义dp[i][j]为字符串s[i-1]和p[j-1]是否能匹配。
  2. 递归式为dp[i][j] = dp[i-1][j-1] && (p[j-1] == . || s[i-1] == p[j-1])
    OR ((dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == .)) || dp[i][j-2]) && p[j-1] == *
    第一种情况为非*，通配一样字符或.
    第二种情况为*，如果通配**（有条件：与p的前一个字符相等或p为.）就是只移动s，dp[i-1][j]。若不通配就只移动p及其前一个字符**。
  3. 方向为从左到右，从上到下。初始值为dp[0][0] = true。以及若s为空，p为多个*时候，dp[0][j]=true。

与Wildcard Matching不同之处用黑体标注了：

  1. 用.代替?
  2. *情况，不匹配p移动两位而不是一位。
  3. *情况，匹配带条件而不是无条件。
  4. 初始化用dp[0][j-2]而不是j-1。

注意事项：

  1. 递归式含*不匹配情况dp[i][j-2]。
  2. 初始化s为空，p为多个*。此情况其实与递归式符合，因为i=1开始，所以i=0的时候，dp[i-1][j]为负值省去，
    只取dp[i][j-2]。
  3. 循环中j按理应该从2开始，因为递归式含p[j-2], 这样要初始化第1列(第0列已经初始化为False)。由于题目条件保证星号前一定有其他字符，所以p的第0位不能是星号，所以j可以从1开始
  4. Python中任何矩阵初始化都只能用两重for循环而不能用乘号

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def isMatch(self, s: str, p: str) -> bool:
	dp = [[False for _ in range((len(p) + 1))] for _ in range(len(s) + 1)]
	dp[0][0] = True
	for j in range(2, len(dp[0])):
		dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'

	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if p[j - 1] != '*':
				dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')
			else:
				dp[i][j] = (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.')) or (dp[i][j - 2])
	return dp[-1][-1]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isMatch(String s, String p) {
	boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
	dp[0][0] = true;
	for(int j = 2; j < dp[0].length; j++)
		if(p.charAt(j-1) == '*') // remember s="", p="a*"
			dp[0][j] = dp[0][j-2];
	for(int i = 1; i < dp.length; i++)
		for(int j = 1; j < dp[0].length; j++) {
			if(p.charAt(j-1) == '*')
				dp[i][j] = (dp[i][j-2] || ((s.charAt(i-1) == p.charAt(j-2) 
				|| p.charAt(j-2) == '.') && dp[i-1][j]));
			else
				dp[i][j] = dp[i-1][j-1] && (s.charAt(i-1) == p.charAt(j-1) 
				|| p.charAt(j-1) == '.');
		}
	return dp[dp.length -1][dp[0].length - 1];
}

算法分析：

时间复杂度为O(n*m)，空间复杂度为O(n*m)。

Free mock interview