97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Code：

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        
        if len(s1)==0:
            return s2==s3
        elif len(s2)==0:
            return s1==s3
        elif len(s3)==0:
            return 0==len(s1)+len(s2)
        elif len(s3)!=len(s1)+len(s2):
            return False
        
        n=len(s1)
        m=len(s2)
        
        dp=[]
        row=[0]*(n+1)
        
        for i in range(m+1):
            dp.append(row[:])
            
        dp[0][0]=1
        
        for j in range(m+1):
            for k in range(n+1):
                if j==0 and k==0:
                    continue
                if j==0 and dp[j][k-1]==1 and s3[j+k-1]==s1[k-1]:
                    dp[j][k]=1
                elif k==0 and dp[j-1][k]==1 and s3[j+k-1]==s2[j-1]:
                    dp[j][k]=1
                elif dp[j-1][k]==1 and s3[j+k-1]==s2[j-1] or dp[j][k-1]==1 and s3[j+k-1]==s1[k-1]:
                    dp[j][k]=1
        
        return dp[m][n]==1