Python solution with detailed explanation

  • 0

    Solution with discussion

    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]
                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)
                    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)

Log in to reply

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