View on NeetCode
View on LeetCode

Problem

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

Example 2:

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

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1, s2, and s3 consist of lowercase English letters.

Solution

Approach: 2D Dynamic Programming

The key insight is that at each position in s3, we check if we can form it by taking a character from s1 or s2, given what we’ve used so far.

Implementation

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n, l = len(s1), len(s2), len(s3)

        # Length check
        if m + n != l:
            return False

        # dp[i][j] = can we form s3[0:i+j] using s1[0:i] and s2[0:j]
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        # Fill first column (only using s1)
        for i in range(1, m + 1):
            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]

        # Fill first row (only using s2)
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]

        # Fill rest of table
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                k = i + j - 1  # Current position in s3

                # Can we match by taking from s1?
                if s1[i-1] == s3[k]:
                    dp[i][j] = dp[i][j] or dp[i-1][j]

                # Can we match by taking from s2?
                if s2[j-1] == s3[k]:
                    dp[i][j] = dp[i][j] or dp[i][j-1]

        return dp[m][n]

Approach 2: Space-Optimized 1D DP

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n, l = len(s1), len(s2), len(s3)

        if m + n != l:
            return False

        dp = [False] * (n + 1)

        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 and j == 0:
                    dp[j] = True
                elif i == 0:
                    dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
                elif j == 0:
                    dp[j] = dp[j] and s1[i-1] == s3[i-1]
                else:
                    k = i + j - 1
                    dp[j] = (dp[j] and s1[i-1] == s3[k]) or \
                            (dp[j-1] and s2[j-1] == s3[k])

        return dp[n]

Approach 3: Recursion with Memoization

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

        memo = {}

        def dp(i, j):
            k = i + j

            if k == len(s3):
                return True

            if (i, j) in memo:
                return memo[(i, j)]

            result = False

            # Try taking from s1
            if i < len(s1) and s1[i] == s3[k]:
                result = result or dp(i + 1, j)

            # Try taking from s2
            if j < len(s2) and s2[j] == s3[k]:
                result = result or dp(i, j + 1)

            memo[(i, j)] = result
            return result

        return dp(0, 0)

Complexity Analysis

2D DP:

• Time Complexity: O(m * n), where m and n are lengths of s1 and s2.
• Space Complexity: O(m * n) for the dp table.

1D DP:

• Time Complexity: O(m * n).
• Space Complexity: O(n), only one row at a time.

Key Insights

1. Length Constraint: s3 length must equal s1 length + s2 length.

2. DP State: dp[i][j] = can we form s3[0:i+j] using first i chars of s1 and first j chars of s2.

3. Two Choices: At each position in s3, we can take the next character from s1 or s2 (if it matches).

4. Position Mapping: Position k in s3 corresponds to using i chars from s1 and j chars from s2, where k = i + j - 1.

5. Base Cases:
   • dp[0][0] = True (empty strings interleave to empty)
   • First row: can only use s2
   • First column: can only use s1
6. Order Preservation: Characters from s1 and s2 must maintain their relative order in s3.