O(m) space and O(mn) time solution using DP


  • 0
    B
    class Solution:
        # @return a boolean
        def isInterleave(self, s1, s2, s3):
            l1, l2, l3 = len(s1), len(s2), len(s3)
            
            if l1 + l2 != l3:
                return False
    
            # initialize first row
            dp = [True]
            for j in xrange(l2):
                if dp[j] is True and s2[j] == s3[j]:
                    dp.append(True)
                else:
                    dp.append(False)
            
            for i in xrange(l1):
                dp[0] = True if dp[0] is True and s1[i] == s3[i] else False
    
                for j in xrange(l2):
                    if (dp[j+1] is True and s1[i] == s3[i+j+1]) or (dp[j] is True and s2[j] == s3[i+j+1]):
                        dp[j+1] = True
                    else:
                        dp[j+1] = False
    
            return dp[-1]
    

    We can use a matrix to store True/False about the subproblem, but we only need dp[i-1][j] and dp[i][j-1] to calculate dp[i][j], so it reduced to an array to store only dp[j].


  • 0
    F

    Great solutions!


Log in to reply
 

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