Python recursive w/memoization, 96.6%


  • 0
    A
    class Solution(object):
        # generic memoization wrapper
        def memoize(func):
            memo={}
            def wrapper(*args):
                if args in memo: return memo[args]
                res=func(*args)
                memo[args]=res
                return res
            return wrapper
            
        @memoize
        def isInterleave(self, s1, s2, s3):
            if len(s1) == len(s2) == len(s3) == 0 : return True
            if len(s3) == 0 : return False
            res = False
            
            if len(s1) > 0 and s1[0] == s3[0] : 
                res = res or self.isInterleave(s1[1:],s2,s3[1:])
                
            if len(s2) > 0 and s2[0] == s3[0] : 
                res = res or self.isInterleave(s1,s2[1:],s3[1:])
                
            return res
            
            
    

Log in to reply
 

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