KK's blog

每天积累多一些

0%

LeetCode 044 Wildcard Matching

Posted on Edited on Disqus:

LeetCode 044 Wildcard Matching

<div>

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

<pre>'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). </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 <font face="monospace">?</font> 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 = "" Output: true Explanation: '' matches any sequence. </pre>

Example 3:

<pre>Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'. </pre>

Example 4:

<pre>Input: s = "adceb" p = "ab" Output: true Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce". </pre>

Example 5:

<pre>Input: s = "acdcb" p = "a*c?b" Output: false </pre>

</div>

题目大意：

通配符外卡匹配问题，有特殊字符"*"和"?"，其中"?" 能代替任何字符，"*"能代替任何字符串。

解题思路：

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

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

注意事项：

  1. 递归式含*不匹配情况dp[i][j-1]，容易忽略。
  2. 初始化s为空，p为多个*。根据递归式来写，i=0时，递归式只剩下dp[i][j-1]。将i = 0带入到内外循环代码实现即可(先写内外循环)
  3. 模板问题： dp初始化先col再row； i循环到len(dp)而不是len(s); 用到p时候是p[i - 1]而不是p[i]

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)] # remember p then s
	dp[0][0] = True
	for j in range(1, len(dp[0])):
		if p[j - 1] == '*':
			dp[0][j] = dp[0][j - 1]
	for i in range(1, len(dp)): # remember len(dp) not len(s)
		for j in range(1, len(dp[0])):
			if p[j - 1] != '*': # remember j-1 not j
				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] or dp[i][j - 1]
	return dp[-1][-1]

注意事项：

  1. 递归式含*不匹配情况dp[i][j-1]，我写的时候忽略了。
  2. 初始化s为空，p为多个*。此情况其实与递归式符合，因为i=1开始，所以i=0的时候，dp[i-1][j]为负值省去，
    只取dp[i][j-1]。
  3. 一开始写的corner case并入到递归式处理。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isMatch(String s, String p) {
	//if(s.isEmpty() && p.isEmpty())
		//return true;
	//if(!s.isEmpty() && p.isEmpty())
		//return false;
	//if(s.isEmpty() && !p.isEmpty() && isAllStars(p))
		//return true;
	//if(s.isEmpty() && !p.isEmpty())
		//return false;
	
	boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
	dp[0][0] = true;
	for(int j = 1; j < dp[0].length; j++)
		// remember empty s can match any prefix *** character in p making sure dp[0][j] = true
		if(p.charAt(j-1) == '*')
			dp[0][j] = dp[0][j-1];
	for(int i = 1; i < dp.length; i++)
		for(int j = 1; j < dp[0].length; j++)
			dp[i][j] = (dp[i-1][j-1] && (p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1)))
			// miss dp[i][j-1] means no match on *
			|| ((dp[i-1][j] || dp[i][j-1]) && p.charAt(j-1) == '*'); 
	return dp[dp.length -1][dp[0].length - 1];
}

算法分析：

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

Free mock interview