Interleaving String (LeetCode 97): From Recursion to a 1D DP Table
5 views
Given strings s1, s2, and s3, decide whether s3 is formed by interleaving s1 and s2: taking all characters of both, keeping each string's internal order, and merging them. For example, s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" returns true, while s3 = "aadbbbaccc" returns false.
Why greedy fails
A natural idea is to walk s3 and take the next character from whichever string matches. When both s1 and s2 offer the same character, you have to choose, and a wrong choice can fail later even though another path succeeds. That branching is the signal to use dynamic programming.
Quick length check
If len(s1) + len(s2) != len(s3), return false immediately. Interviewers like seeing this early exit.
Define the state
Let dp[i][j] be true if the first i characters of s1 and the first j characters of s2 can interleave to form the first i + j characters of s3.
Base case: dp[0][0] = true.
Transition: dp[i][j] is true if either
- dp[i-1][j] is true and s1[i-1] == s3[i+j-1] (the last character came from s1), or
- dp[i][j-1] is true and s2[j-1] == s3[i+j-1] (the last character came from s2).
The answer is dp[len(s1)][len(s2)].
Python with one row
def is_interleave(s1, s2, s3):
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:
from_s1 = i > 0 and dp[j] and s1[i-1] == s3[i+j-1]
from_s2 = j > 0 and dp[j-1] and s2[j-1] == s3[i+j-1]
dp[j] = from_s1 or from_s2
return dp[n]
Before updating, dp[j] still holds the previous row's value (dp[i-1][j]), and dp[j-1] already holds the current row's value (dp[i][j-1]), which is exactly what the transition needs. Time is O(m*n), space O(n). You can swap the strings so the row uses the shorter one.
The memoized recursion alternative
You can also write a recursive function f(i, j) that tries both options and caches results. It is often easier to derive in an interview: start with plain recursion, notice repeated (i, j) pairs, add a cache, then convert to a table if asked. Each step is a natural improvement you can narrate.
Edge cases
- Empty strings: s1 = "", s2 = "", s3 = "" is true.
- One empty input: the answer is simply whether the other equals s3.
- Repeated characters, which create the branching that breaks greedy.
Why it's a good interview question
It tests whether you recognize the "two sequences, choose from either" pattern shared with edit-distance-style problems, but the state here is about prefixes consumed, not operations. Explaining what dp[i][j] means in plain English is half of a strong answer.
Support during the interview
When you're defining DP states live, it's easy to get tangled. Linkjob AI (https://linkjob.ai) provides real-time help during live job interviews and technical interviews, offering hints and structure while you work through the solution yourself.