Python solution with detailed explanation


  • 0
    G

    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)
    

Log in to reply
 

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