Interleaving String
Problem
Given three strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2, and false otherwise.
- 0 ≤ s1.length, s2.length ≤ 100
- 0 ≤ s3.length ≤ 200
- s1, s2, and s3 consist of lowercase English letters.
Example
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"trueThe string s3 can be formed by interleaving s1 and s2 as follows: take 'a' from s1, then 'a' from s1, then 'd' from s2, then 'b' from s2, then 'b' from s1, then 'c' from s2, then 'b' from s1, then 'c' from s1, then 'a' from s2, then 'c' from s1. This preserves the order of characters in s1 and s2.
Approach
Straightforward Solution
A brute-force approach tries all possible ways to interleave s1 and s2 to form s3, which leads to exponential time complexity due to the combinatorial explosion of choices.
Core Observation
The problem reduces to verifying if s3 can be formed by choosing characters sequentially from s1 and s2 without reordering either string. The key is that the sum of lengths of s1 and s2 must equal the length of s3, and at each step, the next character in s3 must match the next character in either s1 or s2.
Path to Optimal
Recognizing overlapping subproblems and optimal substructure, the problem can be solved with dynamic programming. Define a state dp(i, j) representing whether s3[:i+j] can be formed by interleaving s1[:i] and s2[:j]. The solution builds on smaller subproblems by checking if the current character of s3 matches the next character of s1 or s2 and recursively verifying the remainder.
Optimal Approach
Use top-down memoized recursion (DP) with a helper function dp(i, j) that returns true if s3[:i+j] is an interleaving of s1[:i] and s2[:j]. The function checks base cases, memoizes results to avoid recomputation, and explores both possibilities of taking the next character from s1 or s2 if they match s3. This approach runs in O(n*m) time and space, where n and m are lengths of s1 and s2.
Time
O(n * m)
Each state (i, j) is computed once and stored in memo. There are at most n * m states, where n and m are lengths of s1 and s2.
Space
O(n * m)
The memo dictionary stores results for each state (i, j), requiring O(n * m) auxiliary space. The recursion stack depth is at most n + m, which is bounded by O(n + m).
Pattern Spotlight
Dynamic Programming (Top-Down Memoization for Sequence Interleaving)
When verifying if one sequence can be formed by interleaving two others while preserving order, model the problem as a state machine over indices and use memoization to avoid exponential recomputation of overlapping subproblems.
Solution
| 1 | class Solution:
|
| 2 | def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
|
| 3 | if len(s1) + len(s2) != len(s3):
|
| 4 | return False
|
| 5 |
|
| 6 | memo = {}
|
| 7 |
|
| 8 | def dp(i, j):
|
| 9 | if i == len(s1) and j == len(s2):
|
| 10 | return True
|
| 11 | if (i, j) in memo:
|
| 12 | return memo[(i, j)]
|
| 13 |
|
| 14 | k = i + j
|
| 15 | res = False
|
| 16 | if i < len(s1) and s1[i] == s3[k]:
|
| 17 | res = dp(i + 1, j)
|
| 18 |
|
| 19 | if not res and j < len(s2) and s2[j] == s3[k]:
|
| 20 | res = dp(i, j + 1)
|
| 21 |
|
| 22 | memo[(i, j)] = res
|
| 23 | return res
|
| 24 |
|
| 25 | return dp(0, 0) |
Step-by-Step Solution
Validate Lengths and Initialize Memoization Cache
| 3 | if len(s1) + len(s2) != len(s3):
|
| 4 | return False
|
| 6 | memo = {}
|
Objective
To quickly rule out impossible cases by comparing lengths and prepare a cache to store intermediate results.
Key Insight
If the combined lengths of s1 and s2 do not equal s3's length, s3 cannot be an interleaving, allowing an immediate return of false. Initializing a memo dictionary enables caching of subproblem results, which is essential to avoid redundant recursive calls and exponential blowup.
Interview Quick-Check
Core Logic
Checking length equality is a necessary precondition for interleaving; failing this check immediately prunes impossible inputs.
Common Pitfalls & Bugs
Forgetting this length check leads to unnecessary computation and incorrect results on invalid inputs.
State & Boundaries
Memoization cache keys are tuples (i, j) representing indices in s1 and s2, ensuring unique states.
Recursively Explore Interleaving Possibilities with Memoization
| 8 | def dp(i, j):
|
| 9 | if i == len(s1) and j == len(s2):
|
| 10 | return True
|
| 11 | if (i, j) in memo:
|
| 12 | return memo[(i, j)]
|
| 14 | k = i + j
|
| 15 | res = False
|
| 16 | if i < len(s1) and s1[i] == s3[k]:
|
| 17 | res = dp(i + 1, j)
|
| 19 | if not res and j < len(s2) and s2[j] == s3[k]:
|
| 20 | res = dp(i, j + 1)
|
| 22 | memo[(i, j)] = res
|
| 23 | return res
|
Objective
To determine if s3 can be formed by interleaving s1 and s2 starting from indices i and j, using memoization to avoid repeated work.
Key Insight
The recursive function dp(i, j) checks if the substring s3[i+j:] can be formed by interleaving s1[i:] and s2[j:]. It returns true if both s1 and s2 are fully consumed. At each step, it tries to match the next character of s3 with the next character of s1 or s2, recursively exploring both options if valid. Memoization stores results of (i, j) states to prevent recomputation, turning an exponential search into polynomial time.
Interview Quick-Check
Core Logic
The recursion explores two branches: advancing in s1 if s1[i] matches s3[i+j], or advancing in s2 if s2[j] matches s3[i+j], returning true if either leads to a valid interleaving.
State & Boundaries
Base case occurs when i and j reach the ends of s1 and s2, indicating successful interleaving.
Common Pitfalls & Bugs
Failing to check memo before recursion leads to redundant computations and timeouts.
Complexity
Memoization ensures each state is computed once, bounding time complexity to O(n*m).
Return Final Interleaving Result from Initial State
| 25 | return dp(0, 0) |
Objective
To start the recursive exploration from the beginning of both strings and return the final boolean result.
Key Insight
The initial call dp(0, 0) represents the full problem: can s3 be formed by interleaving all of s1 and s2? This triggers the entire memoized recursion, and the returned boolean indicates the answer.
Interview Quick-Check
Core Logic
Starting recursion at indices (0, 0) covers the entire strings and initiates the DP exploration.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
if (i, j) in memo:Check if the current state (i, j) has been computed before.
Memoization lookup prevents redundant recursive calls, drastically reducing time complexity.
if len(s1) + len(s2) != len(s3):Check if combined lengths of s1 and s2 equal length of s3.
This is a fundamental feasibility check; if lengths don't match, s3 cannot be an interleaving, allowing immediate termination.
if i == len(s1) and j == len(s2):Check if both s1 and s2 have been fully consumed.
Reaching the end of both strings means a successful interleaving has been found, serving as the base case for recursion.
return memo[(i, j)]Return the cached result for the current state.
Returning memoized results ensures each state is computed once, enabling efficient DP.
res = dp(i + 1, j)Recursively call dp advancing index i in s1.
This explores the path where the next character of s3 comes from s1, building the solution incrementally.
res = dp(i, j + 1)Recursively call dp advancing index j in s2.
This explores the alternative path where the next character of s3 comes from s2, ensuring all possibilities are considered.
return FalseReturn false if lengths do not match.
Returning early here prevents unnecessary computation on impossible inputs, improving efficiency.
memo = {}Initialize a memo dictionary to cache results of subproblems.
Memoization is essential to avoid exponential recomputation of overlapping subproblems, enabling polynomial time complexity.
return TrueReturn true if base case is met.
This terminates the recursion successfully, signaling that s3 is an interleaving of s1 and s2.
if i < len(s1) and s1[i] == s3[k]:Check if next character in s1 matches current character in s3.
Matching characters allow advancing in s1, exploring one branch of the interleaving possibility.
memo[(i, j)] = resCache the result for the current state (i, j).
Storing the result prevents recomputation of this state in future recursive calls, enabling efficient memoization.
return dp(0, 0)Start the recursion from the beginning of s1 and s2.
This initiates the DP exploration covering the entire problem space, producing the final answer.
def dp(i, j):Define the recursive helper function dp with indices i and j.
This function encapsulates the state of the problem as the current positions in s1 and s2, enabling systematic exploration of interleaving possibilities.
if not res and j < len(s2) and s2[j] == s3[k]:If res is still false, check if next character in s2 matches current character in s3.
This conditional ensures the second branch is only explored if the first branch failed, optimizing recursion.
return resReturn the result for the current state.
Returning the computed boolean value propagates the success or failure up the recursion stack.
k = i + jCalculate the current index k in s3 as the sum of i and j.
The index k aligns the position in s3 with the combined progress in s1 and s2, maintaining synchronization.
res = FalseInitialize result variable res as false.
Starting with false ensures that only successful recursive paths set res to true.
Test Your Understanding
Why is memoization critical in this recursive solution for interleaving strings?
Because without memoization, the recursion explores the same (i, j) states multiple times, leading to exponential time complexity. Memoization ensures each state is computed once, reducing the complexity to polynomial time.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Interleaving String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Interleaving String drill