Python DFS with memorization

  • 0
    class Solution(object):
        def isMatch(self, s, p):
            i = j = 0
            cache = [[-1 for _ in range(len(p))] for _ in range(len(s))]
            return self.helper(s,p,i,j,cache)
        def helper(self, s, p, i, j, cache):
            if i==len(s) and j==len(p):
                return True
            elif j==len(p): 
                return True if s[i:].count("*") == len(s)-i else False  
            elif i==len(s):
                return True if p[j:].count("*") == len(p)-j else False        
            elif cache[i][j]!=-1: return cache[i][j]
                if s[i]==p[j]:
                    cache[i][j] = self.helper(s,p,i+1,j+1,cache)
                    if s[i]=='*' or p[j]=='*':
                        cache[i][j] = self.helper(s,p,i,j+1,cache) or self.helper(s,p,i+1,j,cache) or self.helper(s,p,i+1,j+1,cache)
                    elif s[i]=='?' or p[j]=='?':
                        cache[i][j] = self.helper(s,p,i+1,j+1,cache)
                        cache[i][j] = False
                return cache[i][j]

Log in to reply

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