97. Interleaving String - Explanation

Description

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 <= 100
0 <= s3.length <= 200

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the length of the string s1 and n is the length of the string s2.

Hint 1

If the sum of the characters in s1 and s2 does not equal s3, we return false. Think in terms of recursion and visualize it as a decision tree, where we explore different combinations of portions from both strings. Can you determine the possible decisions at each recursion step?

Hint 2

We recursively iterate through the strings using indices i, j, and k for s1, s2, and s3, respectively. At each step, we extend the current path in two directions based on whether the k-th character of s3 matches the current character of s1 or s2. If any path returns true, we immediately return true. If k goes out of bounds, it means we have successfully formed the interleaved string, so we return true.

Hint 3

This approach is exponential. Can you think of a way to optimize it? Since k depends on i and j, it can be treated as a constant, as we can derive k using i + j.

Hint 4

We can use memoization to cache the results of recursive calls and avoid redundant computations. Treating i and j as states, we can use a hash map or a 2D array to store the results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def isInterleave(self, 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 & Space Complexity

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

Where $m$ is the length of the string $s1$ and $n$ is the length of the string $s2$ .

2. Dynamic Programming (Top-Down)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        dp = {}
        def dfs(i, j, k):
            if k == len(s3):
                return (i == len(s1)) and (j == len(s2))
            if (i, j) in dp:
                return dp[(i, j)]

            res = False
            if i < len(s1) and s1[i] == s3[k]:
                res = dfs(i + 1, j, k + 1)
            if not res and j < len(s2) and s2[j] == s3[k]:
                res = dfs(i, j + 1, k + 1)

            dp[(i, j)] = res
            return res

        return dfs(0, 0, 0)

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of the string $s1$ and $n$ is the length of the string $s2$ .

3. Dynamic Programming (Bottom-Up)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
        dp[len(s1)][len(s2)] = True

        for i in range(len(s1), -1, -1):
            for j in range(len(s2), -1, -1):
                if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
                    dp[i][j] = True
                if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
                    dp[i][j] = True
        return dp[0][0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of the string $s1$ and $n$ is the length of the string $s2$ .

4. Dynamic Programming (Space Optimized)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        if n < m:
            s1, s2 = s2, s1
            m, n = n, m

        dp = [False for _ in range(n + 1)]
        dp[n] = True
        for i in range(m, -1, -1):
            nextDp = [False for _ in range(n + 1)]
            if i == m:
                nextDp[n] = True
            for j in range(n, -1, -1):
                if i < m and s1[i] == s3[i + j] and dp[j]:
                    nextDp[j] = True
                if j < n and s2[j] == s3[i + j] and nextDp[j + 1]:
                    nextDp[j] = True
            dp = nextDp
        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(min(m, n))$

Where $m$ is the length of the string $s1$ and $n$ is the length of the string $s2$ .

5. Dynamic Programming (Optimal)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        if n < m:
            s1, s2 = s2, s1
            m, n = n, m

        dp = [False for _ in range(n + 1)]
        dp[n] = True
        for i in range(m, -1, -1):
            nextDp = True if i == m else False
            for j in range(n, -1, -1):
                res = False if j < n else nextDp
                if i < m and s1[i] == s3[i + j] and dp[j]:
                    res = True
                if j < n and s2[j] == s3[i + j] and nextDp:
                    res = True
                dp[j] = res
                nextDp = dp[j]
        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(min(m, n))$

Where $m$ is the length of the string $s1$ and $n$ is the length of the string $s2$ .