Easy Python Solution with Cache


  • 0
    class Solution(object):
        cache = {}
        def isInterleave(self, s1, s2, s3):
            """
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            """
            if (s1, s2, s3) in self.cache:
                return self.cache[(s1, s2, s3)]
            if len(s1) + len(s2) != len(s3):
                self.cache[(s1, s2, s3)] = False
                return False
            if not s1 and not s2 and not s3:
                return True if not s3 else False
            if s1 and s1[0] == s3[0] and self.isInterleave(s1[1:], s2[:], s3[1:]):
                self.cache[(s1, s2, s3)] = True
                return True
            if s2 and s2[0] == s3[0] and self.isInterleave(s1[:], s2[1:], s3[1:]):
                self.cache[(s1, s2, s3)] = True
                return True
            self.cache[(s1, s2, s3)] = False
            return False
    

Log in to reply
 

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