Interleaving String
Decide whether a string can be formed by interleaving two other strings while preserving each one's character order.
- 0 <= s1.length, s2.length <= 100
- 0 <= s3.length <= 200
- s1, s2, and s3 consist of lowercase English letters.
Intuition
Interleaving string asks whether s3 can be formed by interleaving s1 and s2 while preserving the relative order within each.
A greedy match fails, and seeing why matters. When the next character of s3 matches the next character of both s1 and s2, there is no local information to decide which to consume — and the wrong choice may only fail many characters later. Backtracking on that ambiguity is exponential.
The DP removes it by tracking how much of each string has been used:
- dp[i][j] is true when the first i characters of s1 and first j of s2 can interleave to form the first i + j characters of s3.
That the s3 index is i + j rather than independent is the key economy — the position in s3 is fully determined by how much of each source has been consumed, so no third dimension is needed.
Each state is reachable two ways: take the next character from s1 if it matches s3[i+j-1] and dp[i-1][j] holds, or from s2 under the corresponding condition.
The first check is a length test: if len(s1) + len(s2) != len(s3), return false immediately. Without it the table is malformed and the result meaningless.
The base case dp[0][0] = true says two empty strings interleave to an empty string, and the first row and column handle the cases where one string contributes nothing.
Only the previous row is ever read, so the table collapses to a single row and O(min(m, n)) space.
A 2-D grid where dp[i][j] asks whether the first i of s1 and first j of s2 can build the first i+j of s3. The index i + j - 1 into s3 falls out of that definition — the position in the result is determined by how much of each source has been consumed.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(m*n) time and O(m*n) space.
See why greedy fails
When the next character matches both strings, no local information decides which to take, and the wrong choice may fail much later. That ambiguity is what forces a DP.
Check the lengths first
If len(s1) + len(s2) != len(s3), return false immediately. Without this the table is malformed and every result is meaningless.
Define the two-dimensional state
dp[i][j] is true when the first i of s1 and first j of s2 form the first i + j of s3. The s3 index is determined by i + j, so no third dimension is needed.
Set the base case
dp[0][0] = true — two empty strings interleave to an empty string. The first row and column then cover one string contributing nothing.
Allow both transitions
A state is reachable by taking s1[i-1] when it matches s3[i+j-1] and dp[i-1][j] holds, or by taking s2[j-1] under the matching condition. Either route suffices.
Read the final cell
dp[m][n] answers the question, having consumed both strings entirely. No scan of the table is required.
Cost of the tabulation
Every cell is computed once, giving O(m · n) time and O(m · n) space — reducible to O(min(m, n)) since only the previous row is read.
Solution & live demo
Common pitfalls
Skipping the length check
dp = [[False] * (n + 1) for _ in range(m + 1)]
if m + n != len(s3):
return FalseAn interleaving uses every character of both strings exactly once, so the lengths must add up. Without the guard, dp[m][n] reports on a prefix of s3 and returns true for strings that are too long.
Indexing s3 with i or j alone
s1[i - 1] == s3[i - 1]
s1[i - 1] == s3[i + j - 1]
The character being placed in s3 is at the combined position, since both strings contribute to it. Using one index compares against the wrong character as soon as the other string has contributed anything.
Greedily matching whichever string fits
if s3[k] == s1[i]: i += 1 elif s3[k] == s2[j]: j += 1
dp[i][j] = from_s1 or from_s2
When both strings offer the same next character, the greedy choice may be the wrong one and there's no backtracking. The DP keeps both possibilities alive at every cell.
Edge cases
dp[0][0] is true by definition, giving an immediate true answer
caught by the length check up front, returning false before any DP work
the DP degenerates to a straight character-by-character comparison against the non-empty string
the DP correctly explores both the 'from s1' and 'from s2' branches at each cell, which is exactly where greedy consumption fails