44.py

'''
 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 ? or *.
'''

classSolution(object):
defisMatch(self, s, p):
"""
 :type s: str
 :type p: str
 :rtype: bool
 """

iflen(p) ==0:
returnlen(s) ==0

dp= [[Falsefor_inrange(len(p) +1)] for_inrange(len(s) +1)]
dp[0][0] =True

forindexinrange(1,len(dp[0])):
ifp[index-1] =='*':
dp[0][index] =dp[0][index-1]

forindex_iinrange(1, len(dp)):
forindex_jinrange(1, len(dp[0])):
ifs[index_i-1] ==p[index_j-1] orp[index_j-1] =='?':
dp[index_i][index_j] =dp[index_i-1][index_j-1]
elifp[index_j-1] =='*':
dp[index_i][index_j] =dp[index_i][index_j-1] ordp[index_i-1][index_j]
else:
dp[index_i][index_j] =False
returndp[len(s)][len(p)]