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

  • 0
    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]:
            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
                        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

    Great solutions!

Log in to reply

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