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

Difficulty: interview

Starter code:

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        

Solutions:
class Solution:
     def isInterleave(self, s1, s2, s3):
         """
         :type s1: str
         :type s2: str
         :type s3: str
         :rtype: bool
         """
         if len(s3) != len(s1) + len(s2):
             return False
         if not s1 or not s2:
             return (s1 or s2) == s3
         options = {(0, 0)}
         for char in s3:
             new_options = set()
             for i1, i2 in options:
                 if i1 < len(s1) and char == s1[i1]:
                     new_options.add((i1 + 1, i2))
                 if i2 < len(s2) and char == s2[i2]:
                     new_options.add((i1, i2 + 1))
             options = new_options
             if not options:
                 return False
         return True

class Solution:
     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
         l1,l2,l3 = len(s1)+1, len(s2)+1, len(s3)+1
         
         dp = [True for i in range(l2)]
         for i in range(1,l2):
             dp[i] = dp[i-1] and s2[i-1] == s3[i-1]
         for i in range(1,l1):
             dp[0] = dp[0] and s1[i-1] == s3[i-1]
             for j in range(1, l2):
                 dp[j] = dp[j] and s1[i-1] == s3[i+j-1] or dp[j-1] and s2[j-1] == s3[i+j-1]
                 
         return dp[-1]
     
         # dp = [[True for i in range(l2)] for j in range(l1)]
         # for i in range(1,l1):
         #     dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
         # for j in range(1, l2):
         #     dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
         # for i in range(1,l1):
         #     for j in range(1, l2):
         #         dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i+j-1] or dp[i][j-1] and s2[j-1] == s3[i+j-1]
         # return dp[-1][-1]


class Solution:
     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 and s2 and s3:
             return True if s2 == s3 else False
         if not s2 and s1 and s3:
             return True if s1 == s3 else False
         if not s1 and not s2 and not s3:
             return True
         if (s1 and s2 and not s3) or (not s1 and not s2 and s3):
             return False
 
         result = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
         result[0][0] = True
         for i in range(len(s1) + 1):
             il_idx = i - 1
             for j in range(len(s2) + 1):
                 if i == j == 0:
                     continue
                 if j > len(s3) - 1:
                     break
                 s1_idx, s2_idx = i - 1, j - 1
                 s1_char = s1[s1_idx] if s1_idx > -1 else None
                 s2_char = s2[s2_idx] if s2_idx > -1 else None
                 il_char = s3[il_idx + j]
                 top = False if i == 0 else result[i - 1][j]
                 left = False if j == 0 else result[i][j - 1]
                 ds = set()
                 if not left:
                     ds.add(s1_char)
                 if not top:
                     ds.add(s2_char)
                 result[i][j] = il_char in ds and (top or left)
                 if (s1_char == s2_char == il_char) and top and left:
                     result[i][j] = True
                 #print(f" [{i},{j}] ==> checking if ** {il_char} **  in  {ds} ==> set result to {result[i][j]}")
         #print(result)
         return result[-1][-1]
                 
                 
                 
                 
                 
                 
                 


class Solution:
     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
         
         m, n = len(s1) + 1, len(s2) + 1
         dp = [[False] * n for _ in range(m)]
         
         dp[0][0] = True
         for row in range(1, m):
             dp[row][0] = dp[row - 1][0] and s1[row - 1] == s3[row - 1]
         
         for col in range(1, n):
             dp[0][col] = dp[0][col - 1] and s2[col - 1] == s3[col - 1]
         
         for row in range(1, m):
             for col in range(1, n):
                 # print(row, col)
                 # print(s1[row - 1])
                 # print(s2[col - 1])
                 # print(s3[row + col - 1])
                 dp[row][col] = (dp[row - 1][col] and s1[row - 1] == s3[row + col - 1]) \
                                or (dp[row][col - 1] and s2[col - 1] == s3[row + col - 1])
         
         # print(dp)
         
         return dp[-1][-1]


class Solution:
     def isInterleave(self, s1, s2, s3):
         l1, l2 = len(s1), len(s2)
         if len(s3)!=l1+l2: return False
         if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         dp = [[False]*(l2+1) for _ in range(l1+1)]
         dp[0][0] = True
         for i in range(l1):
             if s1[i]==s3[i]: dp[i+1][0]=True
             else: break
         for i in range(l2):
             if s2[i]==s3[i]: dp[0][i+1]=True
             else: break
         for i in range(1, l1+1):
             for j in range(1, l2+1):
                 dp[i][j] = (s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1])
         return dp[-1][-1]

class Solution:
     def isInterleave(self, s1, s2, s3):
         """
         :type s1: str
         :type s2: str
         :type s3: str
         :rtype: bool
         """
         if len(s3) != len(s1) + len(s2): return False
         if '' in [s1, s2]: return s3 == s1+s2
         
         dp = [[False]*(len(s2)+1) for _ in range(len(s1)+1)]
         for i in range(len(s1)+1):
             for j in range(len(s2)+1):
                 if i == 0 and j == 0: 
                     dp[i][j] = True
                 else:
                     dp[i][j] = False
                     if j > 0: dp[i][j] |= dp[i][j-1] and s2[j-1] == s3[i+j-1]
                     if i > 0: dp[i][j] |= dp[i-1][j] and s1[i-1] == s3[i+j-1]                    
         return dp[-1][-1]

class Solution:
     def isInterleave(self, s1, s2, s3):
         """
         :type s1: str
         :type s2: str
         :type s3: str
         :rtype: bool
         """
         if not s1:
             if s2 != s3:
                 return False
             else:
                 return True
         if not s2:
             if s1 != s3:
                 return False
             else:
                 return True
         if len(s1) + len(s2) != len(s3):
             return False
         f = [[False for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
         f[0][0] = True
         for i in range(1, len(s1) + 1):
             if s1[i - 1] == s3[i - 1] and f[i - 1][0]:
                 f[i][0] = True
         for j in range(1, len(s2) + 1):
             if s2[j - 1] == s3[j - 1] and f[0][j - 1]:
                 f[0][j] = True
         for i in range(1, len(s1) + 1):
             for j in range(1, len(s2) + 1):
                 f[i][j] = (f[i - 1][j] and (s3[i + j - 1] == s1[i - 1])) or ((s3[i + j - 1] == s2[j - 1]) and f[i][j - 1])
         return f[-1][-1]

class Solution:
     def isInterleave(self, s1, s2, s3):
         # Solution 1
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # dp = [[False]*(l2+1) for _ in range(l1+1)]
         # dp[0][0] = True
         # for i in range(l1):
         #     if s1[i]==s3[i]: dp[i+1][0]=True
         #     else: break
         # for i in range(l2):
         #     if s2[i]==s3[i]: dp[0][i+1]=True
         #     else: break
         # for i in range(1, l1+1):
         #     for j in range(1, l2+1):
         #         dp[i][j] = (s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1])
         # return dp[-1][-1]
         
         # Solution 2
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # dp = [False]*(l2+1)
         # dp[0] = True
         # for i in range(l2):
         #     if s2[i]==s3[i]: dp[i+1]=True
         #     else: break
         # for i in range(1, l1+1):
         #     for j in range(l2+1):
         #         dp[j] = (s1[i-1]==s3[i+j-1] and dp[j]) or (j-1>=0 and s2[j-1]==s3[i+j-1] and dp[j-1])
         # return dp[-1]
     
         # Solution 3
         l1, l2 = len(s1), len(s2)
         if len(s3)!=l1+l2: return False
         if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         options = {(0, 0)}
         for c in s3:
             new_options = set()
             for (i1, i2) in options:
                 if i1<l1 and s1[i1]==c: new_options.add((i1+1, i2))
                 if i2<l2 and s2[i2]==c: new_options.add((i1, i2+1))
             if not new_options: return False
             options = new_options
         return True
                 
         


class Solution:
     def bruteForce(self, s1, s2, s3, i, j, k, string, m):
         try:
             return m[(i,j)]
         except KeyError:  
             if k >= len(s3):
                 if string == s3:
                     m[(i,j)] = True
                     return True
                 else:
                     m[(i,j)] = False
                     return False
             else:
                 x = False
                 y = False
                 xstring = string[:]
                 if i < len(s1):
                     if(s1[i] == s3[k]):
                         if not string: string  = s1[i]
                         else: string  = string + s1[i]
                         x = self.bruteForce(s1, s2, s3, i+1, j, k+1, string, m)
                         if x == True:
                             m[(i,j)] = True
                             return True
                 if j < len(s2):
                     if(s2[j] == s3[k]):
                         if not xstring: xstring = s2[j]
                         else: xstring = xstring + s2[j]
                         y = self.bruteForce(s1, s2, s3, i, j+1, k+1, xstring, m)
                 m[(i,j)] = x or y
                 return x or y
 
     def isInterleave(self, s1, s2, s3):
         """
         :type s1: str
         :type s2: str
         :type s3: str
         :rtype: bool
         """
         if not s1 and not s2 and not s3: return True
         if not s1:
             if s2 == s3: return True
             else: return False
         if not s2:
             if s1 == s3: return True
             else: return False
         if len(s3) != len(s1) + len(s2): return False
         return self.bruteForce(s1,s2,s3,0,0,0, "", {})


class Solution:
     def isInterleave(self, s1, s2, s3):
         if s1=='' and s2=='' and s3=='':
             return True
         if len(s1)+len(s2)!=len(s3):
             return False
         paths = [[False for i in range(len(s1)+1)] for j in range(len(s2)+1)]
         for i in range(1, len(s1)+1):
             if s1[i-1] == s3[i-1]:
                 paths[0][i] = True
             else:
                 break
         for i in range(1, len(s2)+1):
             if s2[i-1] == s3[i-1]:
                 paths[i][0] = True
             else:
                 break
         for i in range(1, len(s2)+1):
             for j in range(1, len(s1)+1):
                 if ((paths[i][j-1] is True and s1[j-1]==s3[i+j-1] )
                         or
                     (paths[i-1][j] is True and s2[i-1]==s3[i+j-1])
                 ):
                     paths[i][j]=True
         return paths[len(s2)][len(s1)]

class Solution:
     def isInterleave(self, s1, s2, s3):
         # Solution 1
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # dp = [[False]*(l2+1) for _ in range(l1+1)]
         # dp[0][0] = True
         # for i in range(l1):
         #     if s1[i]==s3[i]: dp[i+1][0]=True
         #     else: break
         # for i in range(l2):
         #     if s2[i]==s3[i]: dp[0][i+1]=True
         #     else: break
         # for i in range(1, l1+1):
         #     for j in range(1, l2+1):
         #         dp[i][j] = (s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1])
         # return dp[-1][-1]
         
         # Solution 2
         l1, l2 = len(s1), len(s2)
         if len(s3)!=l1+l2: return False
         if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         dp = [False]*(l2+1)
         dp[0] = True
         for i in range(l2):
             if s2[i]==s3[i]: dp[i+1]=True
             else: break
         for i in range(1, l1+1):
             for j in range(l2+1):
                 dp[j] = (s1[i-1]==s3[i+j-1] and dp[j]) or (j-1>=0 and s2[j-1]==s3[i+j-1] and dp[j-1])
         return dp[-1]
     
         # Solution 3
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # options = {(0, 0)}
         # for c in s3:
         #     new_options = set()
         #     for (i1, i2) in options:
         #         if i1<l1 and s1[i1]==c: new_options.add((i1+1, i2))
         #         if i2<l2 and s2[i2]==c: new_options.add((i1, i2+1))
         #     if not new_options: return False
         #     options = new_options
         # return True
                 
         


class Solution:
     def isInterleave(self, s1, s2, s3):
         # Solution 1
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # dp = [[False]*(l2+1) for _ in range(l1+1)]
         # dp[0][0] = True
         # for i in range(l1):
         #     if s1[i]==s3[i]: dp[i+1][0]=True
         #     else: break
         # for i in range(l2):
         #     if s2[i]==s3[i]: dp[0][i+1]=True
         #     else: break
         # for i in range(1, l1+1):
         #     for j in range(1, l2+1):
         #         dp[i][j] = (s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1])
         # return dp[-1][-1]
         
         # Solution 2
         l1, l2 = len(s1), len(s2)
         if len(s3)!=l1+l2: return False
         if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         dp = [False]*(l2+1)
         dp[0] = True
         for i in range(l2):
             if s2[i]==s3[i]: dp[i+1]=True
             else: break
         for i in range(1, l1+1):
             for j in range(l2+1):
                 dp[j] = (s1[i-1]==s3[i+j-1] and dp[j]) or (j-1>=0 and s2[j-1]==s3[i+j-1] and dp[j-1])
         return dp[-1]
     
         # Solution 3
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # options = {(0, 0)}
         # for c in s3:
         #     new_options = set()
         #     for (i1, i2) in options:
         #         if i1<l1 and s1[i1]==c: new_options.add((i1+1, i2))
         #         if i2<l2 and s2[i2]==c: new_options.add((i1, i2+1))
         #     if not new_options: return False
         #     options = new_options
         # return True
                 
         


class Solution:
     def isInterleave(self, s1, s2, s3):
         # Solution 1
         l1, l2 = len(s1), len(s2)
         if len(s3)!=l1+l2: return False
         if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         dp = [[False]*(l2+1) for _ in range(l1+1)]
         dp[0][0] = True
         for i in range(l1):
             if s1[i]==s3[i]: dp[i+1][0]=True
             else: break
         for i in range(l2):
             if s2[i]==s3[i]: dp[0][i+1]=True
             else: break
         for i in range(1, l1+1):
             for j in range(1, l2+1):
                 dp[i][j] = (s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1])
         return dp[-1][-1]
         
         # Solution 2
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # dp = [False]*(l2+1)
         # dp[0] = True
         # for i in range(l2):
         #     if s2[i]==s3[i]: dp[i+1]=True
         #     else: break
         # for i in range(1, l1+1):
         #     for j in range(l2+1):
         #         dp[j] = (s1[i-1]==s3[i+j-1] and dp[j]) or (j-1>=0 and s2[j-1]==s3[i+j-1] and dp[j-1])
         # return dp[-1]
     
         # Solution 3
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # options = {(0, 0)}
         # for c in s3:
         #     new_options = set()
         #     for (i1, i2) in options:
         #         if i1<l1 and s1[i1]==c: new_options.add((i1+1, i2))
         #         if i2<l2 and s2[i2]==c: new_options.add((i1, i2+1))
         #     if not new_options: return False
         #     options = new_options
         # return True
                 
         


class Solution:
 
     def qute_print(self, A):
         for row in A:
             for elem in row:
                 print('{:2}'.format(elem), end=' ')
             print()
 
     def isInterleave(self, A, B, C):
         n, m = len(A), len(B)
 
         if len(C) != n + m:
             return False
 
         dp = [[False] * (m + 1) for _ in range(n + 1)]
         dp[0][0] = True
 
         for i in range(1, n + 1):
             dp[i][0] = bool(dp[i - 1][0] * (A[i - 1] == C[i - 1]))
 
         for j in range(1, m + 1):
             dp[0][j] = bool(dp[0][j - 1] * (B[j - 1] == C[j - 1]))
 
 
         for i in range(1, n + 1):
             for j in range(1, m + 1):
                 if A[i - 1] == C[i + j - 1]:
                     dp[i][j] = dp[i - 1][j]
                 if not dp[i][j] and B[j - 1] == C[i + j - 1]:
                     dp[i][j] = dp[i][j - 1]
 
 
                 # if A[i-1] == C[i+j-1] and B[j - 1] != C[i + j - 1]:
                 #     dp[i][j] = dp[i - 1][j]
                 # elif A[i - 1] != C[i + j - 1] and B[j - 1] == C[i + j - 1]:
                 #     dp[i][j] = dp[i][j - 1]
                 # elif A[i - 1] == C[i + j - 1] and B[j - 1] == C[i + j - 1]:
                 #     dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
 
         return dp[-1][-1]


class Solution:
     def isInterleave(self, s1, s2, s3):
         # Solution 1
         l1, l2 = len(s1), len(s2)
         if len(s3)!=l1+l2: return False
         if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         dp = [[False]*(l2+1) for _ in range(l1+1)]
         dp[0][0] = True
         for i in range(l1):
             if s1[i]==s3[i]: dp[i+1][0]=True
             else: break
         for i in range(l2):
             if s2[i]==s3[i]: dp[0][i+1]=True
             else: break
         for i in range(1, l1+1):
             for j in range(1, l2+1):
                 dp[i][j] = (s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1])
         return dp[-1][-1]
         
         # Solution 2
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # dp = [False]*(l2+1)
         # dp[0] = True
         # for i in range(l2):
         #     if s2[i]==s3[i]: dp[i+1]=True
         #     else: break
         # for i in range(1, l1+1):
         #     for j in range(l2+1):
         #         dp[j] = (s1[i-1]==s3[i+j-1] and dp[j]) or (j-1>=0 and s2[j-1]==s3[i+j-1] and dp[j-1])
         # return dp[-1]
     
         # Solution 3
         # l1, l2 = len(s1), len(s2)
         # if len(s3)!=l1+l2: return False
         # if l1==0 or l2==0: return (l1 and s1==s3) or (l2 and s2==s3) or not s3
         # options = {(0, 0)}
         # for c in s3:
         #     new_options = set()
         #     for (i1, i2) in options:
         #         if i1<l1 and s1[i1]==c: new_options.add((i1+1, i2))
         #         if i2<l2 and s2[i2]==c: new_options.add((i1, i2+1))
         #     if not new_options: return False
         #     options = new_options
         # return True
                 
         


class Solution:
     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
         
         res = [[False for j in range(1+len(s2))] for i in range(1+len(s1))]
         for i in range(1+len(s1)):
             for j in range(1+len(s2)):
                 if i == 0 and j == 0:
                     res[i][j] = True
                 elif i == 0:
                     res[i][j] = res[i][j-1] and s3[i+j-1] == s2[j-1]
                 elif j == 0:
                     res[i][j] = res[i-1][j] and s3[i+j-1] == s1[i-1]
                 else:
                     res[i][j] = res[i][j] or (s3[i+j-1] == s1[i-1] and res[i-1][j])
                     res[i][j] = res[i][j] or (s3[i+j-1] == s2[j-1] and res[i][j-1])
         return res[len(s1)][len(s2)]