Interleaving String
Decide whether a string can be formed by interleaving two other strings while preserving each one's character order.
Open on LeetCode ↗Intuition
The natural instinct is to greedily consume whichever of s1 or s2 matches the next character of s3, but that breaks the moment both strings offer the same next character -- there is no way to know locally which one to take, and a wrong guess can doom the rest even though a valid interleaving existed. This needs DP over the pair (i, j): dp[i][j] means the first i characters of s1 and the first j characters of s2 can together interleave to form the first i+j characters of s3. A cell is reachable from above if the matching s1 character lines up, or from the left if the matching s2 character lines up -- checking both possibilities is exactly what greedy single-choice consumption cannot do. Always check len(s1) + len(s2) == len(s3) first, or the DP can fill every cell and still land on a wrong answer.
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
Check the length invariant first
If len(s1) + len(s2) does not equal len(s3), no interleaving is possible regardless of character content, so return false immediately without building the DP table.
Build a 2D table of reachability
Create dp[i][j] for i from 0 to len(s1) and j from 0 to len(s2), with dp[0][0] = True as the base case: two empty prefixes trivially interleave to an empty result.
Fill each cell from its two possible predecessors
For each (i, j), dp[i][j] is true if dp[i-1][j] is true AND s1[i-1] matches s3[i+j-1], OR dp[i][j-1] is true AND s2[j-1] matches s3[i+j-1]. The final answer is dp[len(s1)][len(s2)], which accounts for every possible interleaving path rather than one greedy guess.
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