← Create New Paste

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.
Created Nov 17, 2026 17:58 Expires Nov 17, 2027 17:58