本文主要是介绍LeetCode 44 Wildcard Matching 贪心 DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like?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 = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
--------------------------------------------------
Greedy Solution:
1. There is no need to refresh the status of star, staremerge. Only one star is enough, because the character(for example, 'a') always needs to match some 'a' in s. Matching the former 'a' is better than the latter 'a' in s as is illustrated in the figure. I.e., there is no need to record the matching range for every '*', the latest '*' has the largest range of choice.
2. sbegin is refreshed when mismatch occurs and pbegin is refreshed when meeting new '*';
3. Focusing on s is better than handling the two strings at the same time.
So the final concise code is like:
class Solution:def isMatch(self, s, p):slen, plen, i, j = len(s), len(p), 0, 0star = Falsewhile (i < slen):if (j < plen and (s[i] == p[j] or p[j] == '?')):i += 1j += 1elif (j < plen and p[j] == '*'):star_begin_s = istar_begin_p = j+1j += 1star = Trueelif (star):j = star_begin_pstar_begin_s += 1i = star_begin_selse:return Falsewhile (j < plen and p[j] == '*'):j += 1if (j == plen):return Truereturn False
Using DP, the codes look like:
class Solution {public:bool isMatch(const char *s, const char *p) {int slen = strlen(s), plen = strlen(p), i, j, countp = 0;for (const char *ptr = p; *ptr; ++ptr)if (*ptr != '*')++countp;if (countp > slen)return false;bool dp[500][500];memset(dp,false,sizeof(dp));dp[0][0] = true;for (i = 1; i <= plen; ++i) {dp[i][0] = dp[i - 1][0] && *(p + i -1) == '*';for (j = 1; j <= slen; ++j) {if (*(p + i -1) == '*')dp[i][j] = dp[i][j - 1] || dp[i - 1][j];elsedp[i][j] = dp[i - 1][j - 1] && (*(p + i -1) == *(s + j -1) || *(p + i -1) == '?');}}return dp[plen][slen];}
};DP Solution:
f[i][j] indicates whether p[0..i] matches s[0..j]. So
if p[i] == '*', dp[i][j] = dp[i][j-1] || dp[i-1][j]
if p[i] != '*', dp[i][j] = dp[i-1][j-1] && single match
reduce two-dimension dp to 1 dimension
class Solution:def isMatch(self, s, p):slen, plen = len(s), len(p)if (plen <= 0):return slen == 0if (slen <= 0):return all(pi == '*' for pi in p)f = [p[0] == '*' for i in range(slen)]f[0] = (p[0] == '*' or p[0] == s[0] or p[0] == '?')match_empty = [False for i in range(plen)] #以i结尾的p是否和s的空前缀匹配match_empty[0] = p[0] == '*'for i in range(1, plen):match_empty[i] = (match_empty[i-1] and p[i] == '*')#print(f)for i in range(1, plen):pre = list(f)for j in range(0, slen):if (p[i] == '*'):#f[i][j] = f[i][j-1] || f[i-1][j]tmp2 = f[j-1] if j >= 1 else match_empty[i-1]f[j] = f[j] or tmp2else:#f[i][j] = f[i-1][j-1]match = (p[i] == s[j]) or (p[i] == '?')tmp = pre[j-1] if j >= 1 else match_empty[i-1]f[j] = tmp and match#print(f)return f[-1]
s = Solution()
print(s.isMatch("aa","a"))
print(s.isMatch("aa","aa"))
print(s.isMatch("aaa","a"))
print(s.isMatch("aa","*"))
print(s.isMatch("aa","a*"))
print(s.isMatch("ab","?*"))
print(s.isMatch("aab","c*a*b"))
print(s.isMatch("adceb","*a*b"))
print(s.isMatch("a","a*"))
这篇关于LeetCode 44 Wildcard Matching 贪心 DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
