LeetCode 97: Interleaving String Solution in Python Explained

Problem Statement

In LeetCode 97, you’re given three strings s1, s2, and s3. Your task is to return true if s3 can be formed by interleaving s1 and s2—taking characters from either string in any order, while preserving their original sequence—otherwise, return false. This differs from tree counting like LeetCode 96: Unique Binary Search Trees, focusing on string matching.

Constraints

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• Strings contain only lowercase English letters

Example

Let’s see some cases:

Copy codeInput: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: Interleave: a(a)b(c)c from s1, d(b)b(c)a from s2.

Copy codeInput: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: No valid interleaving matches s3.

Copy codeInput: s1 = "", s2 = "", s3 = ""
Output: true
Explanation: Empty strings interleave to empty.

These examples show we’re validating interleaving possibilities.

Understanding the Problem

How do you solve LeetCode 97: Interleaving String in Python? Take s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac". We need to check if s3 can be built by interleaving s1 and s2—e.g., "a" from s1, "a" from s1, "d" from s2, etc., matching s3. This isn’t a tree generation task like LeetCode 95: Unique Binary Search Trees II; it’s about string sequence validation. We’ll use: 1. Dynamic Programming 2D: O(mn) time, O(mn) space—our best solution. 2. Recursive with Memoization: O(mn) time, O(mn) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Dynamic Programming 2D Approach (Primary)

Explanation

Dynamic Programming 2D uses a 2D table dp[i][j] to represent whether s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j]. Build the table bottom-up, checking matches with s1 or s2 characters. It’s the best solution due to its efficiency, straightforward logic, and optimal space usage for the problem’s constraints.

For s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac":

• dp[i][j] = true if s1[i-1] matches and dp[i-1][j] is true, or s2[j-1] matches and dp[i][j-1] is true.
• Final dp[5][5] = true.

Step-by-Step Example

Example 1: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Goal: Return true.

• Start: m = 5, n = 5, dp = 6x6 table, dp[0][0] = true.
• Step 1: Fill first row (using only s2).
• dp[0][1]: "a" vs. "d" → false.
• Rest false, dp[0] = [true, false, ...].
• Step 2: Fill first column (using only s1).
• dp[1][0]: "a" vs. "a" → true.
• dp[2][0]: "aa" vs. "aa" → true.
• dp[5][0]: "aabcc" vs. "aadbb" → false.
• Step 3: Fill table.
• dp[1][1]: "aa" vs. "d" → "aad" (s1: true, s2: false) → true.
• dp[2][2]: "aab" vs. "db" → "aadbb" (true) → true.
• dp[5][5]: "aabcc" vs. "dbbca" → "aadbbcbcac" (true).
• Finish: dp[5][5] = true, return true.

Example 2: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

Goal: Return false.

• Start: dp[5][5] computed.
• Step: Table shows dp[5][5] = false (no valid path).
• Finish: Return false.

Example 3: s1 = "", s2 = "", s3 = ""

Goal: Return true.

• Start: dp = [true].
• Finish: dp[0][0] = true, return true.

How the Code Works (Dynamic Programming 2D) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef isInterleave(s1: str, s2: str, s3: str) -> bool:
    # Line 1: Get lengths of strings
    m, n = len(s1), len(s2)
    # m = length of s1 (e.g., 5), n = length of s2 (e.g., 5)

    # Line 2: Check total length
    if m + n != len(s3):
        # If s1 + s2 length doesn’t match s3 (e.g., 5+5 ≠ 11), impossible
        return False

    # Line 3: Initialize 2D DP table
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    # Creates (m+1) x (n+1) table (e.g., 6x6 for m=5, n=5)
    # dp[i][j] = true if s3[0:i+j] is interleaving of s1[0:i] and s2[0:j]

    # Line 4: Base case - empty strings
    dp[0][0] = True
    # dp[0][0] = true, empty s1 and s2 interleave to empty s3

    # Line 5: Fill first row (using only s2)
    for j in range(1, n + 1):
        # j = 1 to n (e.g., 1 to 5)
        dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
        # If previous is true and s2 matches s3 (e.g., dp[0][1]: "d" vs. "a" → false)

    # Line 6: Fill first column (using only s1)
    for i in range(1, m + 1):
        # i = 1 to m (e.g., 1 to 5)
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
        # If previous is true and s1 matches s3 (e.g., dp[1][0]: "a" vs. "a" → true)

    # Line 7: Fill rest of the table
    for i in range(1, m + 1):
        # i = length of s1 prefix (e.g., 1 to 5)
        for j in range(1, n + 1):
            # j = length of s2 prefix (e.g., 1 to 5)

            # Line 8: Check if s1 char matches and previous state is valid
            if s1[i-1] == s3[i+j-1]:
                dp[i][j] |= dp[i-1][j]
                # If s1[i-1] matches s3[i+j-1] (e.g., "c" vs. "c"), check dp[i-1][j]
                # |= means OR-equals, updates if true (e.g., dp[5][5] may update)

            # Line 9: Check if s2 char matches and previous state is valid
            if s2[j-1] == s3[i+j-1]:
                dp[i][j] |= dp[i][j-1]
                # If s2[j-1] matches s3[i+j-1] (e.g., "a" vs. "a"), check dp[i][j-1]
                # Combines possibilities from s1 or s2

    # Line 10: Return final result
    return dp[m][n]
    # Returns dp[m][n] (e.g., dp[5][5] = true if s3 is interleaving)

This detailed breakdown clarifies how the 2D DP approach efficiently validates interleaving.

Alternative: Recursive with Memoization Approach

Explanation

Recursive with Memoization checks interleaving by exploring all paths—taking a character from s1 or s2—and caches results to avoid recomputation. It’s a top-down alternative that mirrors the problem’s recursive nature.

For "aabcc", "dbbca", "aadbbcbcac":

• Match "a" from s1, recurse.
• Match "a" from s1, "d" from s2, etc.
• Cache states to optimize.

Step-by-Step Example (Alternative)

For "aabcc", "dbbca", "aadbbcbcac":

• (0,0): "a" (s1) → (1,0), true.
• (1,0): "a" (s1) → (2,0), "d" (s2) → (1,1), true.
• Finish: (5,5) → true.

How the Code Works (Recursive)

Copy codedef isInterleaveRecursive(s1: str, s2: str, s3: str) -> bool:
    if len(s1) + len(s2) != len(s3):
        return False

    memo = {}
    def dp(i: int, j: int) -> bool:
        if i == len(s1) and j == len(s2):
            return True
        if (i, j) in memo:
            return memo[(i, j)]

        if i < len(s1) and s1[i] == s3[i + j]:
            if dp(i + 1, j):
                memo[(i, j)] = True
                return True
        if j < len(s2) and s2[j] == s3[i + j]:
            if dp(i, j + 1):
                memo[(i, j)] = True
                return True
        memo[(i, j)] = False
        return False

    return dp(0, 0)

Complexity

• Dynamic Programming 2D:
• Time: O(m*n) – fills m*n table.
• Space: O(m*n) – 2D array.
• Recursive with Memoization:
• Time: O(m*n) – memoized states.
• Space: O(m*n) – memo cache.

Efficiency Notes

Dynamic Programming 2D is the best solution with O(m*n) time and space, offering a clear, bottom-up approach that’s efficient and intuitive—Recursive with Memoization matches complexity but incurs recursion overhead, making it a solid alternative.

Key Insights

• DP Table: Tracks interleaving states.
• Order Preservation: Key to validity.
• Two Sources: s1 or s2 choices.

Additional Example

For s1 = "ab", s2 = "cd", s3 = "acbd":

• Goal: true.
• DP: dp[2][2] = true (e.g., a-c-b-d).

Edge Cases

• Empty Strings: "", "", "" → true.
• Mismatch Length: "a", "b", "abx" → false.
• Single Char: "a", "", "a" → true.

Both solutions handle these well.

Final Thoughts

LeetCode 97: Interleaving String in Python is a challenging string puzzle. The Dynamic Programming 2D solution excels with efficiency and clarity, while Recursive with Memoization offers a top-down perspective. Want more? Try LeetCode 91: Decode Ways for string decoding or LeetCode 95: Unique Binary Search Trees II for tree generation. Ready to practice? Solve LeetCode 97 on LeetCode with "aabcc", "dbbca", "aadbbcbcac", aiming for true—test your skills now!