@@ -0,0 +1,2012 @@
+class Solution:%0A    %22%22%22%0A    @params s1, s2, s3: Three strings as description.%0A    @return: return True if s3 is formed by the interleaving of%0A             s1 and s2 or False if not.%0A    @hint: you can use %5B%5BTrue%5D * m for i in range (n)%5D to allocate a n*m matrix.%0A    %22%22%22%0A    def isInterleave(self, s1, s2, s3):%0A        # write your code here%0A%0A        # Solution 1 (TLE)%0A        # if (not s1):%0A        #     return s2 == s3%0A        # if (not s2):%0A        #     return s1 == s3%0A        # dp = %5B%5Bc%5D for c in s1%5D%0A        # for i in range(len(s2)):%0A        #     for j in range(len(s1)):%0A        #         if (j == 0):%0A        #             left = %5Bs2%5B:i+1%5D%5D%0A        #         else:%0A        #             left = dp%5Bj - 1%5D%0A        #         tmp = %5B%5D%0A        #         for s in left:%0A        #             if ((s + s1%5Bj%5D) not in tmp):%0A        #                 tmp.append(s + s1%5Bj%5D)%0A        #         if (i == 0 and (s1%5B:j + 1%5D + s2%5Bi%5D) not in tmp):%0A        #             tmp.append(s1%5B:j + 1%5D + s2%5Bi%5D)%0A        #         else:%0A        #             for s in dp%5Bj%5D:%0A        #                 if ((s + s2%5Bi%5D) not in tmp):%0A        #                     tmp.append(s + s2%5Bi%5D)%0A        #         dp%5Bj%5D = tmp%0A        # return s3 in dp%5B-1%5D%0A%0A        # Solution 2%0A        if (not s1):%0A            return s2 == s3%0A        if (not s2):%0A            return s1 == s3%0A        if (len(s3) != (len(s1) + len(s2))):%0A            return False%0A        dp = %5B%5BFalse%5D * (len(s2) + 1) for i in range(len(s1) + 1)%5D%0A        for i in range(1, len(s2) + 1):%0A            if (s2%5B:i%5D == s3%5B:i%5D):%0A                dp%5B0%5D%5Bi%5D = True%0A        for i in range(1, len(s1) + 1):%0A            if (s1%5B:i%5D == s3%5B:i%5D):%0A                dp%5Bi%5D%5B0%5D = True%0A        for i in range(1, len(s1) + 1):%0A            for j in range(1, len(s2) + 1):%0A                if (s1%5Bi - 1%5D == s3%5Bi + j - 1%5D and dp%5Bi - 1%5D%5Bj%5D):%0A                    dp%5Bi%5D%5Bj%5D = True%0A                elif (s2%5Bj - 1%5D == s3%5Bi + j - 1%5D and dp%5Bi%5D%5Bj - 1%5D):%0A                    dp%5Bi%5D%5Bj%5D = True%0A        return dp%5B-1%5D%5B-1%5D%0A

Add solution to lintcode question 29