44. Wildcard Matching
折腾了半天，折腾出一个TLE版本。先去散步，待会再回来看看。其实就是递推公式没写完全对。这题还有空间优化的方法。明天再说吧，今天有点刷不动了。
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if s and not p:
return False
if all([c == "*" for c in p]):
return True
for i in range(len(p)):
if p[i] == "*":
continue
else:
break
if i == 0:
return self.match(s, p)
else:
return self.match(s, p) or self.match(s, p[i:])
def match(self, s, p):
print p
# dp[i][j] if p[:i] match s[:j]
dp = [[False for _ in range(len(s)+1)] for _ in range(len(p)+1)]
dp[0][0] = True # string "" match string ""
for i in range(1, len(p)+1):
for j in range(1, len(s)+1):
if p[i-1] == s[j-1] or p[i-1] == "?":
dp[i][j] = dp[i-1][j-1]
elif p[i-1] == "*":
# * 不会影响前面的匹配状况，但是可以影响后面的匹配状况
# * 匹配 1 到 n个值
for k in range(j, len(s)+1):
dp[i][k] = dp[i][k] or dp[i-1][j-1]
# * 匹配 0 个 值
dp[i][j] = dp[i][j] or dp[i-1][j]
return dp[len(p)][len(s)]
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
# dp[i][j] if p[:i] match s[:j]
dp = [[False for _ in range(len(s)+1)] for _ in range(len(p)+1)]
dp[0][0] = True # string "" match string ""
for i in range(1, len(p)+1):
if p[i-1] == "*":
dp[i][0] = dp[i-1][0]
for j in range(1, len(s)+1):
if p[i-1] == s[j-1] or p[i-1] == "?":
dp[i][j] = dp[i-1][j-1]
elif p[i-1] == "*":
# * 不会影响前面的匹配状况，但是可以影响后面的匹配状况
# dp[i][j-1] 如果这个值为True，那么*就用来match s[i-1]
# dp[i-1][j] 如果这个值为True，那么*就match “” 使得dp[i][j]为True
dp[i][j] = dp[i][j-1] or dp[i-1][j]
return dp[len(p)][len(s)]
