Leetcode 97: Interleaving String

 

1. Problem Summary

You’re given three strings s1, s2, and s3.
Determine whether s3 can be formed by interleaving all characters of s1 and s2, preserving the relative order of characters from each string.

• You cannot reorder characters inside s1 or s2.

• At each step, you choose the next char either from s1 or from s2.

• All characters of s1 and s2 must be used exactly once.

Formally, s3 is an interleaving of s1 and s2 if:

• len(s3) = len(s1) + len(s2), and

• There exists a merge of s1 and s2, preserving internal order of each, that equals s3.

Input:

• s1, s2 with length up to 100

• s3 with length up to 200

Output:

• Boolean: true if s3 is an interleaving of s1 and s2, else false.

The “substring splitting” notation in the statement boils down to this standard definition: merge s1 and s2 in order to get s3.

2. Examples Explanation

Example 1:

Input:
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

Output: true

One valid construction:

• From s1: aa | bc | c

• From s2: dbbc | a

• Interleave: "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac"

Order within each string is preserved, and all characters are used → valid interleaving.

Example 2:

Input:
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"

Output: false

Try to align characters from s1 and s2 to form s3 while preserving order; you eventually hit contradictions (e.g., extra b placement conflicts).
No valid merge exists → not an interleaving.

Example 3:

Input:
s1 = ""
s2 = ""
s3 = ""

Output: true

Empty + empty can form empty; trivial valid interleaving.

3. Approach

Pattern:

This is a classic 2D Dynamic Programming / string DP problem:
“Can we reach position (i, j) in s1, s2 to match prefix of s3?”

Naive Idea:

DFS/backtracking:

• At current indices (i, j, k) (k = i + j in s3):

• If s1[i] == s3[k], move to (i+1, j, k+1).

• If s2[j] == s3[k], move to (i, j+1, k+1).

• Explore all paths.

This is exponential without memoization.

4. Optimal Idea: DP on Prefixes

High-Level Idea:

Let:

• n1 = len(s1)

• n2 = len(s2)

• n3 = len(s3)

First, if n1 + n2 != n3, return false (length mismatch).

Define:

• dp[i][j] = true if the first i chars of s1 and first j chars of s2
  can interleave to form the first i + j chars of s3.

We want dp[n1][n2].

Transitions:

At (i, j):

• We are matching s3[i + j - 1] (0-based index).

• Two possibilities:

1. Take from s1:

• If i > 0 and dp[i-1][j] is true and s1[i-1] == s3[i + j - 1],
  then dp[i][j] = true.

2. Take from s2:

• If j > 0 and dp[i][j-1] is true and s2[j-1] == s3[i + j - 1],
  then dp[i][j] = true.

So:

dp[i][j]=(dp[i-1][j]∧s1[i-1]=s3[i+j-1])∨(dp[i][j-1]∧s2[j-1]=s3[i+j-1])

Base:

• dp[0][0] = true (empty + empty = empty)

• dp[i][0]: must match only from s1

• dp[0][j]: must match only from s2

Follow-up: O(|s2|) Space

We can compress the 2D DP into 1D:

• Use dp[j] for the current i row.

• dp[j] represents dp[i][j].

• Update from left to right:

dp[j] = (

    (i > 0 and dp[j]   and s1[i-1] == s3[i + j - 1]) OR

    (j > 0 and dp[j-1] and s2[j-1] == s3[i + j - 1])

)

Where dp[j] before update is actually dp[i-1][j].

Pseudo-code:

Complexity Analysis:

Let n1 = len(s1), n2 = len(s2).

• Time Complexity:

• We fill an (n1+1) x (n2+1) grid, each cell in O(1).

• Total: O(n1 * n2).

• Space Complexity:

• Full DP table: O(n1 * n2).

• Follow-up (1D compression): O(n2) (or O(min(n1, n2)) if we optimize which dimension we compress).

5. Java code

6. C code

7. C++ code

8. Python code

9. JavaScript code