AC Python DP Solution O(mn) time O(n) space 44ms


  • 1
    def isInterleave(self, s1, s2, s3):
        n, m = len(s1), len(s2)
        if len(s3) != n + m:
            return False
        f = [True] + [False] * n
        for i in xrange(n):
            f[i + 1] = f[i] and s1[i] == s3[i]
        for j in xrange(m):
            f[0] = f[0] and s2[j] == s3[j]
            for i in xrange(n):
                f[i + 1] = (f[i] and s1[i] == s3[i + j + 1]) or (f[i + 1] and s2[j] == s3[i + j + 1])
        return f[n]
    
    
    # 101 / 101 test cases passed.
    # Status: Accepted
    # Runtime: 44 ms
    # 99.37%
    

    The idea is to consider where the last letter of S3 come from. The dp process is just like finding maximum path in a matrix when only going right or down is allowed. Instead of keeping the m by n matrix, we just need to keep one row to calculate the next row. In fact, the "next" row can be merged into the current row since each cell is only used by itself (going down) or by its next neighbor (going right).


  • 0

    @dietpepsi Got exactly your runtime with my solution

    class Solution(object):
        def isInterleave(self, s1, s2, s3, memo={}):
            if len(s1) + len(s2) != len(s3): return False
            if not s1 and not s2 and not s3: return True
            if (s1, s2, s3) in memo: return memo[s1, s2, s3]
            memo[s1,s2,s3] =\
                   (len(s1) > 0 and len(s3) > 0 and s1[0] == s3[0] and self.isInterleave(s1[1:], s2, s3[1:], memo)) or\
                   (len(s2) > 0 and len(s3) > 0 and s2[0] == s3[0] and self.isInterleave(s1, s2[1:], s3[1:], memo))
            return memo[s1,s2,s3]
                    
    

Log in to reply
 

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