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
My code:
class Solution:
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
if len(s3)==0:
return True
if len(s3)!=len(s1)+len(s2):
return False
record=[1 for i in range(len(s2)+1)]
for i in range(len(s1)+1):
for j in range(len(s2)+1):
if i==0 and j==0:
record[j]=1
elif i==0:
record[j]=record[j-1] and s2[j-1]==s3[i+j-1]
elif j==0:
record[j]=record[j] and s1[i-1]==s3[i+j-1]
else:
record[j]=(record[j] and s1[i-1]==s3[i+j-1]) or (record[j-1] and s2[j-1]==s3[i+j-1])
print(record)
if len(s2)==0:
return s3==s1
return bool(record[len(s2)])
Solution: https://leetcode.com/problems/interleaving-string/