Python Tabulate + Memo with Explanations. PS Memo should be TLE/rated easy imo


  • 0
    H

    Python Memo(O 2^N)

    Our recursive/memoized answer should be rated as an easy question.

    There are three variables, i, j, k for the current index of s1, s2, and s3 respectively.

    Either s1[i] == s3[k] or s2[j] == s3[k] otherwise it's immediately false because the formed string is a sequence and must be consecutive and not a subsequence.

    In the case that s1[i] == s2[j], we need to try out both ways.

    Thus the worst case is 2^N as there can possibly be two choices at every letter of s3.

    Thus, S3[k] == S1[i] and recur(i+1, j, k+1) or S3[k] == S2[j] and recur(i, j+1, k+1), must reach the end, otherwise False.

    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            if len(s1) + len(s2) != len(s3):
                return False
            return self.can(s1, s2, s3, dict())
        
        def can(self, s1, s2, s3, cache):
            if len(s1) == 0 and len(s2) == 0 and len(s3) == 0:
                return True
            if len(s3) == 0:
                return False
            if (s1, s2, s3) in cache:
                return cache[(s1, s2, s3)]
        
            take_s1 = False
            take_s2 = False
            if len(s1) > 0 and s1[0] == s3[0]:
                take_s1 = self.can(s1[1:], s2, s3[1:], cache)
            if len(s2) > 0 and s2[0] == s3[0]:
                take_s2 = self.can(s1, s2[1:], s3[1:], cache)
            
            cache[(s1,s2,s3)]  = take_s1 or take_s2
            return cache[(s1,s2,s3)]
    

    Python Tabulate: O(len(s1) * len(s2)

    Our tabulated DP answer is a little trickier, but follows the same properties as other string matching questions.

    We have to form a table of i+1 * j+1 length where i and j corresponds to the length of s1 and s2
    and s1[i-1] is the current letter in i and s2[j-1] is the current letter in j so that our dp table can account for empty strings.

    Note that i+j-1 is the character k that we want to match in S3.

    Our base case is that dp[0][0] == True because if we have no elements from either string, we form the empty string.

    Next, we need to consider what it means if j == 0 or i == 0. This means that we are only taking from one string, thus if j == 0: look at if s1[i] matches s3[i] and so forth.

    Our tricky case is if i>0 and j>0. We need to look at if dp[i-1][j] is True or dp[i][j-1] is True and if so, the newly added letter is also == the new length of s3.

    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            if len(s1) == 0:
                return s2 == s3
            if len(s2) == 0:
                return s1 == s3
            if len(s3) != len(s1) + len(s2):
                return False
                
            dp = [[None for i in range(len(s2)+1)] for j in range(len(s1)+1)]
            
            for i in range(len(dp)):
                for j in range(len(dp[0])):
                    if i == 0 and j == 0:
                        dp[i][j] = True
                    elif i == 0:
                        dp[i][j] = dp[i][j-1] and s2[j-1] == s3[j-1]
                    elif j == 0:
                        dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i-1]
                    else:
                        if dp[i-1][j] == True and s3[i+j-1] == s1[i-1]:
                            dp[i][j] = True
                        elif dp[i][j-1] == True and s3[i+j-1] == s2[j-1]:
                            dp[i][j] = True
                        else:
                            dp[i][j] = False
            return dp[-1][-1]
            
    
    
    

Log in to reply
 

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