2020-10-28

Description:

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

Output: false

Solutions: 递归

class Solution:

    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:

        if len(s1)+len(s2) != len(s3): # corner cases

            return False

       

        dp = [[None for j in range(len(s1)+1)] for i in range(len(s2)+1)]

        dp[-1][-1] = True # The Destination should be True

       

        def search(cnt,row,col):

            if dp[row][col] != None:

                return dp[row][col]

           

            if row < len(s2) and s2[row] == s3[cnt] and search(cnt+1,row+1,col): # move downward

                dp[row][col] = True

                return True

            if col < len(s1) and s1[col] == s3[cnt] and search(cnt+1,row,col+1): # move right

                dp[row][col] = True

                return True

            dp[row][col] = False # fail to find a path

            return False

       

        return search(0,0,0)

        # print("\n-------------------------")

        # for d in dp:

        #    print(d)

Runtime: 36 ms, faster than 88.84% of Python3 online submissions for Interleaving String.

Memory Usage: 13.6 MB, less than 5.07% of Python3 online submissions for Interleaving String.