# Python solution with detailed explanation

• Solution with discussion https://discuss.leetcode.com/topic/75386/python-solution-with-detailed-explanation

Wildcard Matching https://leetcode.com/problems/wildcard-matching/

Memoization: O(MN)

• There are three important cases: p[j] is "?", p[j] is not in ("?", " * ") and p[j] == " * ". When p[j] is asterix we can either match or reject p[j] leading to two recursive calls.
• The terminating condition are a bit tricky.
• If i and j are both exhausted, then it is clearly a match.
• if j is exhausted, but i is not, then it is clearly not a match.
• if i is exhausted but j is not, then if all the remaining characters in p are asterix, then we still have a match, otherwise not. Example, ("", * ) or ("ho", ho** ).
``````from collections import defaultdict
class Solution(object):
def helper(self, i, j, s, p, cache):
if i == len(s) and j == len(p):
return True
elif i != len(s) and j == len(p):
return False
elif i == len(s) and j != len(p):
return True if p[j:].count("*") == len(p)-j else False
elif i in cache and j in cache[i]:
return cache[i][j]
else:
if p[j] == "?":
cache[i][j] = self.helper(i+1,j+1,s,p,cache)
elif p[j] not in {'?', '*'}:
cache[i][j] = (s[i] == p[j]) and self.helper(i+1,j+1,s,p,cache)
else:
cache[i][j] = self.helper(i, j+1,s,p,cache) or self.helper(i+1, j,s,p,cache)
return cache[i][j]

def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
cache = defaultdict(dict)
return self.helper(0, 0, s, p, cache)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.