97. Interleaving String

2019-08-01

97. Interleaving String

Given _s1_, _s2_, _s3_, find whether _s3_ is formed by the interleaving of _s1_ and _s2_.

Example 1:

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

Example 2:

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

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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
-->