97. Interleaving String
Model: qwen3.5:9b
Topics: String,Dynamic Programming
FAANG asked: 1
Acceptance rate: 32.8%
Problem Breakdown
We are given three strings s1, s2, and s3. The goal is to determine if s3 can be constructed as an interleaving of characters from s1 and s2. Crucially, the relative order of characters within each source string must remain unchanged.
Key Constraints & Edge Cases:
- Length Mismatch: If
len(s1) + len(s2)does not equallen(s3), it is impossible to forms3regardless of content. We should check this immediately for an optimization. - Empty Strings: The problem allows empty inputs (e.g., Example 3). If both source strings are empty, the target must also be empty to return True. Our DP logic naturally handles these if initialized correctly (
dp[0][0] = True). - Characters: Lowercase English letters only; no overflow or negative number concerns.
Intuition
A brute-force approach would try every possible permutation of picking characters from s1 and s2, which leads to exponential time complexity . This is inefficient because we revisit the same states repeatedly (e.g., reaching a specific index in s3 via different paths).
This suggests Dynamic Programming. We can define a state based on how many characters from each source string have been consumed. Let’s say dp[i][j] represents whether it’s possible to form the prefix of length i + j in s3 using the first i characters of s1 and the first j characters of s2.
The transition logic is straightforward:
To reach state (i, j), we could have come from either:
- State
(i-1, j)(we just consumed a character froms1). This requires matchings3[i+j-1]withs1[i-1]. - State
(i, j-1)(we just consumed a character froms2). This requires matchings3[i+j-1]withs2[j-1].
If either path is valid and the characters match, then state (i, j) is True.
Approach
We will use a 2D boolean table of size (len(s1) + 1) x (len(s2) + 1).
- Initialization: Create
dparray filled with False. Setdp[0][0] = Truebecause empty strings can form an empty string. - Base Cases for Rows/Cols: Fill the first row (
s1exhausted, only usings2) and first column (s2exhausted, only usings1). This checks if prefixes ofs3match exactly with one source string alone. - Iteration: Iterate through all valid indices
(i, j). For each cell:- Check validity from top (using
s1) AND check character equality. - OR check validity from left (using
s2) AND check character equality.
- Check validity from top (using
- Result: Return the value at
dp[len(s1)][len(s2)].
Note on Follow-up: While we use space here for clarity, this can be optimized to by observing that row i only depends on row i-1, allowing us to reduce the table to a 1D array.
Complexity Analysis
- Time: where and . We visit each cell in our DP table exactly once, performing constant work per cell.
- Space: for the 2D boolean array.
- Follow-up Optimization: To satisfy the follow-up constraint of using only
O(len(s2))space (or linear with respect to one string), we can reduce this table to a single row, updating values in place while keeping track of diagonal dependencies or swapping rows.
- Follow-up Optimization: To satisfy the follow-up constraint of using only
Solution
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
# Optimization 1: Length check (O(1))
if len(s1) + len(s2) != len(s3):
return False
m, n = len(s1), len(s2)
# dp[i][j] means s3[:i+j] can be formed by interleaving
# s1[:i] and s2[:j]. We use a 2D array for clarity.
# To satisfy the follow-up O(N) space, we could reduce this to 1 row.
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Base case: empty strings form an empty string
dp[0][0] = True
# Initialize first column (only s2 used, s1 exhausted)
for j in range(1, n + 1):
if s3[j - 1] == s2[j - 1]:
dp[0][j] = dp[0][j-1]
# Initialize first row (only s1 used, s2 exhausted)
for i in range(1, m + 1):
if s3[i - 1] == s1[i - 1]:
dp[i][0] = dp[i-1][0]
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
index_s3 = i + j - 1
# Check if we can transition from s2 (left neighbor)
match_from_s2 = dp[i][j-1] and s3[index_s3] == s2[j-1]
# Check if we can transition from s1 (top neighbor)
match_from_s1 = dp[i-1][j] and s3[index_s3] == s1[i-1]
dp[i][j] = match_from_s2 or match_from_s1
return dp[m][n]
# Example usage:
sol = Solution()
print(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac")) # True
Edge Cases Handled
- Length Mismatch: The initial check
len(s1) + len(s2) != len(s3)returns False immediately, preventing index errors and saving time. - Empty Inputs:
- If
s1is empty buts2matchess3, the first column initialization handles this correctly (dp[0][j]). - If both are empty, loops don’t run or return True based on base case logic.
- If
- Partial Matches: The DP table ensures we only proceed if a character match exists from either source string at that specific step.