Interleaving String

Problem Statement

You are given three strings s1, s2, and s3. Return true if s3 is formed by interleaving s1 and s2 together or false otherwise.

Interleaving two strings s and t is done by dividing s and t into n and m substrings respectively, where the following conditions are met

  • |n - m| <= 1, i.e. the difference between the number of substrings of s and t is at most 1.
  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • Interleaving s and t is s1 + t1 + s2 + t2 + ... or t1 + s1 + t2 + s2 + ...

You may assume that s1, s2 and s3 consist of lowercase English letters.

Example 1:

# Input: s1 = "aaaa", s2 = "bbbb", s3 = "aabbbbaa"
# Output: True

Explanation: We can split s1 into ["aa", "aa"], s2 can remain as "bbbb" and s3 is formed by interleaving ["aa", "aa"] and "bbbb".

Example 2:

# Input: s1 = "", s2 = "", s3 = ""
# Output: True

Example 3:

# Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy"
# Output: False

Explanation: We can’t split s3 into ["ab", "xz", "cy"] as the order of characters is not maintained.

Constraints:

  • 0 <= s1.length, s2.length <= 50
  • 0 <= s3.length <= 100

You should aim for a solution with O(m * n) time and O(min(m, n)) space, where m and n are the lengths of s1 and s2 respectively.

Hint 1

Consider using recursion to explore all possible interleavings.

Hint 2

Memoization or dynamic programming can optimize the recursive approach by storing intermediate results.

Hint 3

A 2D DP table can be used to store whether s3[0...i+j] is formed by interleaving s1[0...i] and s2[0...j].

Solution

Recursion

def is_interleave(s1: str, s2: str, s3: str) -> bool:
    def dfs(i, j, k):
        if k == len(s3):
            return (i == len(s1)) and (j == len(s2))


        if i < len(s1) and s1[i] == s3[k]:
            if dfs(i + 1, j, k + 1):
                return True


        if j < len(s2) and s2[j] == s3[k]:
            if dfs(i, j + 1, k + 1):
                return True


        return False


    return dfs(0, 0, 0)

Time complexity: O(2 ^ {m + n}) Space complexity: O(m + n)