Interleaving String

Problem: Interleaving String

For s1, s2 and s3, whether s3 is interleaving string is decided by whether the last character of s3 is the same as the last of s1 or s2 and whether s3 is interleaving after leaving the last same characters.

Code in Python:

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3): return False
        if not s1: return s2 == s3
        if not s2: return s1 == s3

        m, n = len(s1), len(s2)

        dp = [[False] * (n+1) for _ in xrange(m+1)]

        dp[0][0] = True
        for i in xrange(1, m+1):
            dp[i][0] = s1[i-1] == s3[i-1] and dp[i-1][0]
        for j in xrange(1, n+1):
            dp[0][j] = s2[j-1] == s3[j-1] and dp[0][j-1]
        for i in xrange(1, m+1):
            for j in xrange(1, n+1):
                if s1[i-1] == s2[j-1] == s3[i+j-1]: dp[i][j] = dp[i][j-1] or dp[i-1][j]
                elif s1[i-1] == s3[i+j-1]: dp[i][j] = dp[i-1][j]
                elif s2[j-1] == s3[i+j-1]: dp[i][j] = dp[i][j-1]
                else: dp[i][j] = False

        return dp[-1][-1]