LeetCode 044 Wildcard Matching

LeetCode 044 Wildcard Matching

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

‘?’ Matches any single character.
‘‘ Matches any sequence of characters (including the empty sequence).

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:

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

Example 2:

Input:
s = “aa”
p = ““
Output: true
Explanation: ‘‘ matches any sequence.

Example 3:

Input:
s = “cb”
p = “?a”
Output: false
Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.

Example 4:

Input:
s = “adceb”
p = “ab”
Output: true
Explanation: The first ‘‘ matches the empty sequence, while the second ‘‘ matches the substring “dce”.

Example 5:

Input:
s = “acdcb”
p = “ac?b”
*Output: false

题目大意：

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

解题思路：

这是经典题。两字符串匹配题基本就是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])  if p[j-1] != \* 
              dp[i-1][j] || dp[i][j-1]                           if p[j-1] == \*

第一种情况为非*，通配一样字符或?
第二种情况为*，如果通配就是只移动s，dp[i-1][j]。若不通配（通配完）就只移动p。

1. 方向为从左到右，从上到下。初始值为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代码：

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

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)。