Sharing my Python Top-down DP (memoization) solution


  • 0
    class Solution(object):
        def isInterleave(self, s1, s2, s3, memo={}):
            if len(s1) + len(s2) != len(s3):
                return False
            if len(s3) == 0:
                if len(s1) or len(s2):
                    return False
                return True
            if (s1, s2, s3) in memo:
                return memo[s1, s2, s3]
            if not len(s1):
                if s2[0] == s3[0]:
                    memo[s1, s2, s3] = self.isInterleave(s1, s2[1:], s3[1:])
                    return memo[s1, s2, s3]
                memo[s1, s2, s3] = False
                return False
            if not len(s2):
                if s1[0] == s3[0]:
                    memo[s1, s2, s3] = self.isInterleave(s1[1:], s2, s3[1:])
                    return memo[s1, s2, s3]
                memo[s1, s2, s3] = False
                return False
                
            # If here, neither is empty
            
            a, b = False, False
            if s1[0] == s3[0]:
                a = self.isInterleave(s1[1:], s2, s3[1:])
            if not a and s2[0] == s3[0]:
                b = self.isInterleave(s1, s2[1:], s3[1:])
            memo[s1, s2, s3] = a or b
            return memo[s1, s2, s3]

Log in to reply
 

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