Python solution 60ms

  • 1
    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            m = len(s1)
            n = len(s2)
            l = len(s3)
            if l != m+n:
                return False
            dp = [[0] * (n+1) for _ in xrange(m+1)]
            for i in xrange(0,m+1):
                dp[i][0]  = (s1[:i] == s3[:i])
            for j in xrange(0,n+1):
                dp[0][j] = (s2[:j] == s3[:j])
            for i in xrange(1,m+1):
                count = i
                for j in xrange(1,n+1):
                    dp[i][j] = (dp[i-1][j] and (s3[count] == s1[i-1])) or (dp[i][j-1] and (s3[count] == s2[j-1]))
                    count += 1
            return dp[m][n]

Log in to reply

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