LeetCode · #97

Interleaving String Solution

Given s1, s2, and s3, determine if s3 is formed by interleaving s1 and s2 while preserving order.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #97

🏗️

Pattern

DP — 2D interleave

An interleaving of s1 and s2 is formed by choosing characters from each, preserving their order, to form s3. Determine if s3 can be formed this way.

Example

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true

Constraints

• 0 ≤ s1.length, s2.length ≤ 100 • 0 ≤ s3.length ≤ 200

Section Two · Approach 1

Recursion — O(2^(m+n))

At each position in s3, choose the next character from s1 or s2 (if it matches). Recurse on both choices.

Why it works

Exhaustively tries every interleaving in order.

Why we can do better

Problem: Overlapping subproblems — state (i,j) where i = chars used from s1, j = chars used from s2 is recomputed. 2D DP table of (m+1)×(n+1) stores each state once.

Java — Recursive

 class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length()+s2.length() != s3.length()) return false;
return dfs(s1,s2,s3,0,0);
    }
private boolean dfs(String a,String b,String c,int i,int j) {
if (i+j == c.length()) return true;
boolean ok = false;
if (i < a.length() && a.charAt(i)==c.charAt(i+j)) ok = dfs(a,b,c,i+1,j);
if (!ok && j < b.length() && b.charAt(j)==c.charAt(i+j)) ok = dfs(a,b,c,i,j+1);
return ok;
    }
}

Python — Recursive

 class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1)+len(s2) != len(s3): return False def dfs(i,j):
if i+j == len(s3): return True if i < len(s1) and s1[i]==s3[i+j] and dfs(i+1,j): return True if j < len(s2) and s2[j]==s3[i+j] and dfs(i,j+1): return True return False return dfs(0,0)

Metric	Value
Time	O(2^(m+n))
Space	O(m+n)

Section Three · Approach 2

2D DP — O(m·n) time, O(n) space

dp[i][j] = true if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]. Transition: check if the next char of s3 matches the next char of s1 (from above) or s2 (from left).

💡 Mental model: Imagine weaving two colored threads into a single rope. Thread A (s1) and thread B (s2) must maintain their internal order, but you can switch between them at any point. The grid is your loom: moving right = use next char from s2, moving down = use next char from s1. dp[i][j]=true means you can reach position (i,j) on the loom while producing s3 correctly so far.

Algorithm

If len(s1) + len(s2) != len(s3): immediately false.
dp[0][0] = true. Fill first row (s2 prefix matches s3 prefix) and first column (s1 prefix matches s3 prefix).
For i,j: 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]).
Return dp[m][n].

🎯 When to recognize this pattern: "Can string C be formed by interleaving strings A and B?" Two sequences combined into one, maintaining relative order. The grid is indexed by consumption from each source. Related: LC 115 (Distinct Subsequences).

Space optimization: Since each row depends only on the previous row and the current row (left), a 1D array of size (n+1) suffices, similar to other 2D DP optimizations.

Section Four · Trace

Visual Walkthrough

Trace for s1="ab", s2="cd", s3="acbd".

Interleaving String — 2D DP

Section Five · Implementation

Code — Java & Python

Java — 1D DP (space-optimized)

 class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
boolean[] dp = new boolean[n + 1];
for (int i = 0; i <= m; i++)
for (int j = 0; j <= n; j++) {
if (i == 0 && j == 0) dp[j] = true;
else {
boolean top  = i > 0 && dp[j] && s1.charAt(i-1) == s3.charAt(i+j-1);
boolean left = j > 0 && dp[j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
                    dp[j] = top || left;
                }
            }
return dp[n];
    }
}

Python — 1D DP

 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
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 else:
                    top  = i > 0 and dp[j] and s1[i-1] == s3[i+j-1]
                    left = j > 0 and dp[j-1] and s2[j-1] == s3[i+j-1]
                    dp[j] = top or left
return dp[n]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursion	O(2^(m+n))	O(m+n)	Exponential
2D DP	O(m·n)	O(m·n)	Full table
1D DP ← optimal	O(m·n)	O(n)	Single row reused per s1 iteration

Quick reject: If len(s1) + len(s2) != len(s3), immediately return false. This runs in O(1) and avoids allocating the DP table entirely.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty s1	`"", "abc", "abc"`	s3 must equal s2. First row of DP handles this.
Both empty	`"", "", ""`	dp[0]=true. Return true.
Length mismatch	`"a","b","abc"`	1+1≠3 → immediate false.
Same chars different order	`"ab","ab","aabb"`	Both s1,s2 contribute 'a' then 'b'. dp finds valid interleaving.
No valid interleaving	`"ab","cd","abdc"`	'd' requires s2[1] before s2[0]='c' — order violation. dp[m][n]=false.

⚠ Common Mistake: In the 1D DP, forgetting to reset dp[j]=false when neither "top" nor "left" is true. In the 2D version this is automatic (each cell is independent), but in 1D, dp[j] retains the value from the previous row. You must explicitly set dp[j] = top || left, not dp[j] = dp[j] || left.

← Back to DP — 2D problems

LearningTree

LC 97 · Interleaving String — Solution & Explanation | DSA Guide