44 Wild card Matching

leetcode 44题,题目大意是两个字符串s,p,s是原字符串,p是匹配字符串.匹配字符串中*可以代替任意长度字符串(包括空字符串);?可以视作任意单个字符串,下面是一些示例

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

采用的方法毫无疑问就是动态规划,(i,j)代表了s前i个字符和p前j个字符是否匹配,我一开始用的是字典:

class Solution:def isMatch(self, s, p):""":type s: str:type p: str:rtype: bool"""dict_mn = {}m = len(s)n = len(p)dict_mn[(0,0)] = Truefor i in range(1, m+1):dict_mn[(i, 0)] = Falsefor j in range(1, n+1):# for i in range(0, m):pj = p[j-1]if pj == "?":for i in range(0, m+1):dict_mn[(i, j)] = dict_mn.get((i-1, j-1), False)elif pj == "*":for i in range(0, m+1):dict_mn[(i, j)] = dict_mn[(i, j-1)] or dict_mn.get((i-1, j), False)else:for i in range(0, m+1):dict_mn[(i, j)] = dict_mn.get((i-1, j-1), False) and s[i-1] == p[j-1]return dict_mn[(m, n)]

但是提示说内存不足

class Solution:def isMatch(self, s, p):""":type s: str:type p: str:rtype: bool"""m = len(s)n = len(p)dp = [[None for _ in range(n+1)] for _ in range(m+1)]dp[0][0] = Truefor i in range(1, m+1):dp[i][0] = Falsefor j in range(1, n+1):dp[0][j] = dp[0][j-1] and p[j-1] == "*"for j in range(1, n+1):for i in range(1, m+1):pj = p[j-1]if pj == "?":dp[i][j] = dp[i-1][j-1]elif pj == "*":dp[i][j] = dp[i][j-1] or dp[i-1][j]else:dp[i][j] = dp[i-1][j-1] and s[i-1] == p[j-1]return dp[m][n]

这下就没问题了,看见一个很有意思的解法:

class Solution:def isMatch(self, s, p):""":type s: str:type p: str:rtype: bool"""if len(p) == 0:return len(s) == 0i, j, match_s, star_p = 0, 0, -1, -1while i < len(s):if j < len(p) and (s[i] == p[j] or p[j] == '?'):i += 1j += 1elif j < len(p) and p[j] == '*':match_s, star_p = i, jj += 1elif star_p >= 0:i, j = match_s + 1, star_p + 1match_s += 1else:return Falsewhile j < len(p) and p[j] == '*':j += 1return j == len(p)

用了两个变量存储前面的匹配数量,反复迭代,很有想法,如果p中出现两个*号,那么前面的匹配或者是后面的匹配并没有结果上区别.

转载于:https://www.cnblogs.com/mangmangbiluo/p/10148895.html

总结

以上是生活随笔为你收集整理的44 Wild card Matching的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。