237. Interleaving String
🔗 LeetCode Problem: 97. Interleaving String
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, String, DP - Strings
Problem Statement
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 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- The interleaving is
s1 + t1 + s2 + t2 + ...ort1 + s1 + t2 + s2 + ...
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 = "aaadbbbccc"
Output: false
Example 3:
Input: s1 = "", s2 = "b", s3 = "b"
Output: true
Constraints:
- 0 <= s1.length, s2.length <= 100
- 0 <= s3.length <= 200
- s1, s2, and s3 consist of lowercase English letters.
🧒 Let's Build Understanding from Scratch
Forget the formal definition - What does "interleaving" REALLY mean?
Imagine you have two decks of cards:
Deck 1 (s1): [a] [a] [b] [c] [c]
Deck 2 (s2): [d] [b] [b] [c] [a]
You want to create a single line of cards (s3): [a][a][d][b][b][c][b][c][a][c]
Rules:
1. You can ONLY take cards from the TOP of each deck
2. You must maintain the ORDER within each deck
3. You can switch between decks anytime
Question: Can you create s3 by following these rules?
Let's try:
Take from Deck 1: [a] → s3 so far: [a]
Take from Deck 1: [a] → s3 so far: [a][a]
Take from Deck 2: [d] → s3 so far: [a][a][d]
Take from Deck 2: [b] → s3 so far: [a][a][d][b]
Take from Deck 2: [b] → s3 so far: [a][a][d][b][b]
Take from Deck 1: [b] → s3 so far: [a][a][d][b][b][b]?
Wait! s3 should be [a][a][d][b][b][c]... not [b]!
We need [c] next, but Deck 1 has [b] on top, not [c]!
Let me try differently:
Take from Deck 1: [a] → [a]
Take from Deck 1: [a] → [a][a]
Take from Deck 2: [d] → [a][a][d]
Take from Deck 2: [b] → [a][a][d][b]
Take from Deck 2: [b] → [a][a][d][b][b]
Take from Deck 2: [c] → [a][a][d][b][b][c]
Take from Deck 1: [b] → [a][a][d][b][b][c][b]
Take from Deck 2: [a] → [a][a][d][b][b][c][b][a]?
No! s3 needs [c] next, not [a]!
Let's try again more carefully...
This is the ESSENCE of the problem! ✓
🎨 Visual Discovery - Let's Draw It Out
Example 1: Can we make "aadbbcbcac" from "aabcc" and "dbbca"?
Let's trace it like a path:
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
I'll show which string each character comes from:
Position: 0 1 2 3 4 5 6 7 8 9
s3: a a d b b c b c a c
From: s1 s1 s2 s2 s2 s2 s1 s1 s2 s1
Let me verify this works:
s1 pointer at 0: 'a' ✓ matches s3[0]='a', take it! s1→1
s1 pointer at 1: 'a' ✓ matches s3[1]='a', take it! s1→2
s2 pointer at 0: 'd' ✓ matches s3[2]='d', take it! s2→1
s2 pointer at 1: 'b' ✓ matches s3[3]='b', take it! s2→2
s2 pointer at 2: 'b' ✓ matches s3[4]='b', take it! s2→3
s2 pointer at 3: 'c' ✓ matches s3[5]='c', take it! s2→4
s1 pointer at 2: 'b' ✓ matches s3[6]='b', take it! s1→3
s1 pointer at 3: 'c' ✓ matches s3[7]='c', take it! s1→4
s2 pointer at 4: 'a' ✓ matches s3[8]='a', take it! s2→5
s1 pointer at 4: 'c' ✓ matches s3[9]='c', take it! s1→5
Both pointers reached the end! SUCCESS! ✓
Visual:
s1: a a b c c
↓ ↓ ↓ ↓ ↓
s3: a a d b b c b c a c
↓ ↓ ↓ ↓ ↓
s2: d b b c a
Example 2: Can we make "aaadbbbccc" from "aabcc" and "dbbca"?
s1 = "aabcc"
s2 = "dbbca"
s3 = "aaadbbbccc"
Let me try to trace:
s3[0]='a': Could use s1[0]='a' OR we need 3 a's but s1 only has 2!
Already suspicious... let's continue
If I use both a's from s1 for first two positions:
s3: [a][a][a]...
s1 s1 ?
But s1 has no more a's! And s2 starts with 'd', not 'a'!
Can't make the third 'a'! ✗
This is IMPOSSIBLE! ✗
KEY INSIGHT:
Count check! s1 has 2 a's, s2 has 1 a, s3 needs 3 a's
2 + 1 = 3 ✓ count matches
But ORDER matters! We can't rearrange!
The a's in s1 and s2 must appear in s3 in the right positions!
🤔 The Discovery Process - What Makes This Hard?
Observation 1: We Make Choices
At each position in s3, we have a CHOICE:
Position in s3: [a] [a] [d] [b] [b] [c] ...
At s3[0]='a':
Option 1: Take from s1[0]='a' ✓
Option 2: Take from s2[0]='d' ✗ (doesn't match)
→ Must take from s1
At s3[1]='a':
Option 1: Take from s1[1]='a' ✓
Option 2: Take from s2[0]='d' ✗
→ Must take from s1
At s3[2]='d':
Option 1: Take from s1[2]='b' ✗
Option 2: Take from s2[0]='d' ✓
→ Must take from s2
Sometimes both options work!
At some position, suppose s3[i]='b':
s1[current]='b' ✓
s2[current]='b' ✓
Which do we choose?? 🤔
This is the HEART of the problem!
Observation 2: Greedy Doesn't Work!
Example where greedy fails:
s1 = "ab"
s2 = "ac"
s3 = "aacb"
Greedy approach: "Always take first match"
Position 0, s3[0]='a':
s1[0]='a' ✓ matches! Take it (greedy choice)
s1 pointer: 0→1
Position 1, s3[1]='a':
s1[1]='b' ✗ doesn't match
s2[0]='a' ✓ matches! Take it
s2 pointer: 0→1
Position 2, s3[2]='c':
s1[1]='b' ✗
s2[1]='c' ✓ Take it
s2 pointer: 1→2
Position 3, s3[3]='b':
s1[1]='b' ✓ Take it
s1 pointer: 1→2
Success? Both pointers at end! ✓
But wait... let me try different order:
Position 0, s3[0]='a':
s2[0]='a' ✓ Take from s2 this time!
s2 pointer: 0→1
Position 1, s3[1]='a':
s1[0]='a' ✓ Take from s1
s1 pointer: 0→1
Position 2, s3[2]='c':
s1[1]='b' ✗
s2[1]='c' ✓ Take it
s2 pointer: 1→2
Position 3, s3[3]='b':
s1[1]='b' ✓ Take it
s1 pointer: 1→2
Also works! ✓
Multiple solutions exist!
But here's a FAILING case:
s1 = "ab"
s2 = "bc"
s3 = "abbc"
Greedy:
s3[0]='a': Take s1[0]='a', s1→1
s3[1]='b': Take s1[1]='b', s1→2 (greedy)
s3[2]='b': s1 exhausted! s2[0]='b' ✓ s2→1
s3[3]='c': s2[1]='c' ✓ s2→2
SUCCESS! ✓
Actually works...
Let me find a real failing case:
s1 = "abc"
s2 = "bca"
s3 = "abcabc"
Greedy (always prefer s1):
s3[0]='a': s1[0]='a' ✓ s1→1
s3[1]='b': s1[1]='b' ✓ s1→2 (greedy chooses s1)
s3[2]='c': s1[2]='c' ✓ s1→3
s3[3]='a': s1 done! s2[0]='b' ✗ FAIL!
Should have been:
s3[0]='a': s1[0]='a' ✓ s1→1
s3[1]='b': s2[0]='b' ✓ s2→1 (choose s2 instead!)
s3[2]='c': s2[1]='c' ✓ s2→2
s3[3]='a': s2[2]='a' ✓ s2→3
s3[4]='b': s1[1]='b' ✓ s1→2
s3[5]='c': s1[2]='c' ✓ s1→3
SUCCESS! ✓
Greedy FAILS! We need to try BOTH options! 🔑
Observation 3: This Looks Like a Path Problem!
Think of it as a grid:
s2 →
s1 "" d b b c a
↓
"" ? ? ? ? ? ?
a ? ? ? ? ? ?
a ? ? ? ? ? ?
b ? ? ? ? ? ?
c ? ? ? ? ? ?
c ? ? ? ? ? ?
Starting at top-left (0,0):
- Both s1 and s2 at position 0
- s3 at position 0
We can move:
- RIGHT: take character from s2
- DOWN: take character from s1
Goal: reach bottom-right (len(s1), len(s2))
- This means we've used all of s1 and all of s2
- And formed exactly s3!
Let me trace the successful path for Example 1:
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Start: (0,0) → s3[0]='a'
s1[0]='a' ✓ → go DOWN to (1,0)
At (1,0) → s3[1]='a'
s1[1]='a' ✓ → go DOWN to (2,0)
At (2,0) → s3[2]='d'
s1[2]='b' ✗
s2[0]='d' ✓ → go RIGHT to (2,1)
At (2,1) → s3[3]='b'
s1[2]='b' ✓ could go down
s2[1]='b' ✓ could go right
Choose RIGHT to (2,2)
At (2,2) → s3[4]='b'
s2[2]='b' ✓ → go RIGHT to (2,3)
At (2,3) → s3[5]='c'
s2[3]='c' ✓ → go RIGHT to (2,4)
At (2,4) → s3[6]='b'
s1[2]='b' ✓ → go DOWN to (3,4)
At (3,4) → s3[7]='c'
s1[3]='c' ✓ → go DOWN to (4,4)
At (4,4) → s3[8]='a'
s2[4]='a' ✓ → go RIGHT to (4,5)
At (4,5) → s3[9]='c'
s1[4]='c' ✓ → go DOWN to (5,5)
Reached (5,5)! SUCCESS! ✓
This is a PATH-FINDING problem! 🎯
💡 The AHA Moment - Building the Solution
Understanding the State
At any point, we track:
- i: position in s1 (how many chars we've used from s1)
- j: position in s2 (how many chars we've used from s2)
- k: position in s3 (i + j, how many chars we've formed in s3)
Question at state (i, j):
"Can we form s3[0...k-1] using s1[0...i-1] and s2[0...j-1]?"
At (i, j), we need to match s3[k] where k = i + j
We have TWO choices:
Choice 1: Use s1[i]
- Check if s1[i] == s3[k]
- If YES, check if (i+1, j) is possible
Choice 2: Use s2[j]
- Check if s2[j] == s3[k]
- If YES, check if (i, j+1) is possible
If EITHER choice works → we can form s3! ✓
The Recursive Thinking (Natural Way)
Let me write it in plain English first:
isInterleave(i, j):
"Can we make s3 using first i chars of s1 and first j chars of s2?"
Base case:
If i + j == length of s3:
We've matched everything! Return TRUE
If i + j > length of s3:
We've gone too far! Return FALSE
Recursive case:
k = i + j (position in s3)
option1 = FALSE
option2 = FALSE
If i < len(s1) AND s1[i] == s3[k]:
option1 = isInterleave(i+1, j) // Try using s1[i]
If j < len(s2) AND s2[j] == s3[k]:
option2 = isInterleave(i, j+1) // Try using s2[j]
Return option1 OR option2
This is RECURSIVE EXPLORATION! ✓
Let's Trace It By Hand
s1 = "ab"
s2 = "ac"
s3 = "aabc"
Let me trace: isInterleave(0, 0)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
isInterleave(0, 0):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k = 0 + 0 = 0
s3[0] = 'a'
s1[0] = 'a' == 'a' ✓
Try: isInterleave(1, 0)
s2[0] = 'a' == 'a' ✓
Try: isInterleave(0, 1)
Return isInterleave(1,0) OR isInterleave(0,1)
Let me follow first path: isInterleave(1, 0)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k = 1 + 0 = 1
s3[1] = 'a'
s1[1] = 'b' != 'a' ✗
s2[0] = 'a' == 'a' ✓
Try: isInterleave(1, 1)
Return isInterleave(1, 1)
isInterleave(1, 1):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k = 1 + 1 = 2
s3[2] = 'b'
s1[1] = 'b' == 'b' ✓
Try: isInterleave(2, 1)
s2[1] = 'c' != 'b' ✗
Return isInterleave(2, 1)
isInterleave(2, 1):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k = 2 + 1 = 3
s3[3] = 'c'
i = 2 >= len(s1) = 2, can't use s1
s2[1] = 'c' == 'c' ✓
Try: isInterleave(2, 2)
Return isInterleave(2, 2)
isInterleave(2, 2):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i + j = 2 + 2 = 4 = len(s3)
BASE CASE! Return TRUE ✓
Backtrack: TRUE → TRUE → TRUE → TRUE → TRUE
Final answer: TRUE! ✓
Path taken: s1[0] → s2[0] → s1[1] → s2[1]
Formed: 'a' + 'a' + 'b' + 'c' = "aabc" ✓
🔴 Approach 1: Recursion (What We Discovered)
📝 Implementation
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// Quick check: lengths must match
if (s1.length() + s2.length() != s3.length()) {
return false;
}
return helper(s1, s2, s3, 0, 0);
}
private boolean helper(String s1, String s2, String s3, int i, int j) {
int k = i + j; // Position in s3
// Base case: formed entire s3
if (k == s3.length()) {
return true;
}
boolean option1 = false; // Try taking from s1
boolean option2 = false; // Try taking from s2
// Can we take from s1?
if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
option1 = helper(s1, s2, s3, i + 1, j);
}
// Can we take from s2?
if (j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
option2 = helper(s1, s2, s3, i, j + 1);
}
// If EITHER option works, we succeed
return option1 || option2;
}
}
Why This Is Slow
Time Complexity: O(2^(m+n))
At each position, we try 2 options
Total positions: m + n
Total: 2 × 2 × 2 × ... = 2^(m+n)
For m=100, n=100:
2^200 = astronomical!
WAY TOO SLOW! ❌
Notice: We visit same (i,j) state multiple times!
This is PERFECT for memoization! →
🟡 Approach 2: Memoization (Caching Results)
🎯 What Do We Memoize?
State: (i, j)
i = position in s1
j = position in s2
Question: "Can we form s3[0...i+j-1] using s1[0...i-1] and s2[0...j-1]?"
memo[i][j] = answer for this state
Once computed, reuse it! ✓
📝 Implementation
class Solution {
private Boolean[][] memo;
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
// memo[i][j] = can we form s3 using first i of s1, first j of s2
memo = new Boolean[s1.length() + 1][s2.length() + 1];
return helper(s1, s2, s3, 0, 0);
}
private boolean helper(String s1, String s2, String s3, int i, int j) {
int k = i + j;
if (k == s3.length()) {
return true;
}
// Check memo
if (memo[i][j] != null) {
return memo[i][j];
}
boolean result = false;
// Try s1
if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
result = helper(s1, s2, s3, i + 1, j);
}
// Try s2 (if s1 didn't work)
if (!result && j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
result = helper(s1, s2, s3, i, j + 1);
}
memo[i][j] = result;
return result;
}
}
📊 Complexity
Time: O(m × n) - Each state computed once
Space: O(m × n) - Memo table
🟢 Approach 3: Bottom-Up DP (Building the Grid)
🎯 Understanding dp[i][j]
dp[i][j] = TRUE if we can form s3[0...i+j-1]
using s1[0...i-1] and s2[0...j-1]
Building from bottom-up:
Start with base case: dp[0][0] = TRUE
Build row by row, column by column
At dp[i][j], we ask:
"Did we arrive here from dp[i-1][j] or dp[i][j-1]?"
From dp[i-1][j]: we just used s1[i-1]
→ Check if s1[i-1] == s3[i+j-1]
From dp[i][j-1]: we just used s2[j-1]
→ Check if s2[j-1] == s3[i+j-1]
📝 Implementation
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;
// dp[i][j] = can form s3[0...i+j-1] using s1[0...i-1] and s2[0...j-1]
boolean[][] dp = new boolean[m + 1][n + 1];
// Base case
dp[0][0] = true;
// Fill first column (only using s1)
for (int i = 1; i <= m; i++) {
dp[i][0] = dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1);
}
// Fill first row (only using s2)
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1);
}
// Fill rest of table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int k = i + j - 1; // Position in s3
// Can we come from top (using s1[i-1])?
boolean fromS1 = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(k);
// Can we come from left (using s2[j-1])?
boolean fromS2 = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(k);
dp[i][j] = fromS1 || fromS2;
}
}
return dp[m][n];
}
}
🔍 Complete Dry Run
s1 = "ab", s2 = "ac", s3 = "aabc"
Build dp table:
"" a c
"" T ? ?
a ? ? ?
b ? ? ?
Step 1: Base case
dp[0][0] = TRUE (empty strings)
Step 2: First column (only s1)
dp[1][0]: s1[0]='a' == s3[0]='a' AND dp[0][0]=T → TRUE
dp[2][0]: s1[1]='b' == s3[1]='a'? NO → FALSE
"" a c
"" T
a T
b F
Step 3: First row (only s2)
dp[0][1]: s2[0]='a' == s3[0]='a' AND dp[0][0]=T → TRUE
dp[0][2]: s2[1]='c' == s3[1]='a'? NO → FALSE
"" a c
"" T T F
a T
b F
Step 4: Fill rest
dp[1][1]: k=1+1-1=1, s3[1]='a'
From s1: dp[0][1]=T AND s1[0]='a'=='a' → TRUE
From s2: dp[1][0]=T AND s2[0]='a'=='a' → TRUE
Result: TRUE OR TRUE = TRUE
dp[1][2]: k=1+2-1=2, s3[2]='b'
From s1: dp[0][2]=F → FALSE
From s2: dp[1][1]=T AND s2[1]='c'=='b'? NO → FALSE
Result: FALSE
dp[2][1]: k=2+1-1=2, s3[2]='b'
From s1: dp[1][1]=T AND s1[1]='b'=='b' → TRUE
From s2: dp[2][0]=F → FALSE
Result: TRUE
dp[2][2]: k=2+2-1=3, s3[3]='c'
From s1: dp[1][2]=F → FALSE
From s2: dp[2][1]=T AND s2[1]='c'=='c' → TRUE
Result: TRUE
Final table:
"" a c
"" T T F
a T T F
b F T T
Answer: dp[2][2] = TRUE ✓
📊 Complexity
Time: O(m × n)
Space: O(m × n)
💻 Complete Working Code
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
return bottomUpDP(s1, s2, s3);
}
// Approach 3: Bottom-Up DP - O(m×n)
private boolean bottomUpDP(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length())
return false;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
}
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int k = i + j - 1;
boolean fromS1 = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(k);
boolean fromS2 = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(k);
dp[i][j] = fromS1 || fromS2;
}
}
return dp[m][n];
}
// Approach 2: Memoization - O(m×n)
private Boolean[][] memo;
private boolean memoization(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
memo = new Boolean[s1.length() + 1][s2.length() + 1];
return helperMemo(s1, s2, s3, 0, 0);
}
private boolean helperMemo(String s1, String s2, String s3, int i, int j) {
int k = i + j;
if (k == s3.length())
return true;
if (memo[i][j] != null)
return memo[i][j];
boolean result = false;
if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
result = helperMemo(s1, s2, s3, i + 1, j);
}
if (!result && j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
result = helperMemo(s1, s2, s3, i, j + 1);
}
memo[i][j] = result;
return result;
}
// Approach 1: Recursion - O(2^(m+n))
private boolean recursion(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
return helperRecursion(s1, s2, s3, 0, 0);
}
private boolean helperRecursion(String s1, String s2, String s3, int i, int j) {
int k = i + j;
if (k == s3.length())
return true;
boolean option1 = false, option2 = false;
if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
option1 = helperRecursion(s1, s2, s3, i + 1, j);
}
if (j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
option2 = helperRecursion(s1, s2, s3, i, j + 1);
}
return option1 || option2;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.isInterleave("aabcc", "dbbca", "aadbbcbcac") == true);
System.out.println(s.isInterleave("aabcc", "dbbca", "aaadbbbccc") == false);
System.out.println(s.isInterleave("", "b", "b") == true);
System.out.println(s.isInterleave("ab", "ac", "aabc") == true);
}
}
🔑 Key Insights
The Journey
1. Card deck analogy → understand the problem
2. Trace examples by hand → discover patterns
3. Notice it's path-finding → grid visualization
4. Try greedy → realize it fails
5. Need to try both → recursion
6. Same states repeat → memoization
7. Bottom-up table → optimal DP
Natural progression! ✓
🎪 Memory Aid
"Two decks, one line!"
"Take from top, keep order!"
"Grid path from (0,0) to (m,n)!"
"Try both directions, pick what works!" ✨
📝 Quick Revision
🎯 Core Concept
Problem: Can s3 be formed by interleaving s1 and s2?
Key: Maintain order within s1 and s2
State: (i, j) = positions in s1 and s2
Choice: Use s1[i] or s2[j] for s3[i+j]
⚡ Quick Solution
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
// return recursive(s1, s2, s3, 0, 0);
// Boolean[][] memo = new Boolean[s1.length() + 1][s2.length() + 1];
// return topDown(s1, s2, s3, 0, 0, memo);
return bottomUp(s1, s2, s3);
}
private boolean bottomUp(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
// step 2: base case 1
dp[0][0] = true;
// step 3: consider only s2 with no chars from s1 (2nd if condition).
for (int j = 1; j <= len2; j++) {
dp[0][j] = (s2.charAt(j - 1) == s3.charAt(j - 1)) && dp[0][j - 1];
}
// step 4: consider only s1 with no chars from s2 (1st if condition).
for (int i = 1; i <= len1; i++) {
dp[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1)) && dp[i - 1][0];
}
// step 1: same as top down
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
boolean s1_pick = false;
boolean s2_pick = false;
if (s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
s1_pick = dp[i - 1][j];
}
if (s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
s2_pick = dp[i][j - 1];
}
dp[i][j] = s1_pick || s2_pick;
}
}
return dp[len1][len2];
}
private boolean topDown(String s1, String s2, String s3, int i, int j, Boolean[][] memo) {
if (i + j == s3.length()) {
return true;
}
if (memo[i][j] != null) {
return memo[i][j];
}
boolean s1_pick = false;
boolean s2_pick = false;
if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
s1_pick = topDown(s1, s2, s3, i + 1, j, memo);
}
if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
s2_pick = topDown(s1, s2, s3, i, j + 1, memo);
}
return memo[i][j] = s1_pick || s2_pick;
}
private boolean recursive(String s1, String s2, String s3, int i, int j) {
// step 3: base case
if (i + j == s3.length()) {
return true;
}
boolean s1_pick = false;
boolean s2_pick = false;
// step 1: if char of s1 at i matches with s3 at
// k = (i+j), proced with next character of s1
if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
s1_pick = recursive(s1, s2, s3, i + 1, j);
}
// step 2: if char of s2 at j matches with s3 at
// k = (i+j), proced with next character of s2
if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
s2_pick = recursive(s1, s2, s3, i, j + 1);
}
return s1_pick | s2_pick;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.isInterleave("aabcc", "dbbca", "aadbbcbcac") == true);
System.out.println(s.isInterleave("aabcc", "dbbca", "aadbbbaccc") == false);
System.out.println(s.isInterleave("", "", "") == true);
System.out.println(s.isInterleave("a", "b", "a") == false);
}
}
Complexity: O(m × n) time and space
🎉 Congratulations!
You've learned through: - ✅ Real-world analogies (card decks!) - ✅ Hand-traced examples - ✅ Visual grid paths - ✅ Natural discovery (greedy fails → try both) - ✅ Step-by-step building
No algorithm jumping - pure intuition! 🚀✨