Interleaving String
Problem Description
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:
- s = s1 + s2 + ... + sn
- t = t1 + t2 + ... + tm
|n - m| <= 1- The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...
Note: a + b is the concatenation of strings a and b.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
Constraints:
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1,s2, ands3consist of lowercase English letters.
Follow up: Could you solve it using only O(s2.length) additional memory space?
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
The recursive approach attempts to build the interleaved string one character at a time. At each step, we decide whether to take the next character from s1 or s2, and check recursively if taking that character leads to a solution. If both choices are possible, we try both.
Steps:
- Define a recursive function that takes three indices, one for each of
s1,s2, ands3. - If both indices for
s1ands2are at the start of their respective strings ands3is also at the beginning, thens1ands2are interleavings3. - If the current character of
s1matches withs3, make a recursive call by incrementing the index ofs1ands3. - If the current character of
s2matches withs3, make a recursive call by incrementing the index ofs2ands3. - If either of the recursive calls return true, then
s1ands2can interleaves3.
Code:
- Time Complexity: O(2^(m+n)), where m and n are the lengths of
s1ands2respectively. The recursive tree depth ism + n. - Space Complexity: O(m+n), which is the maximal depth of recursive calls.
2. Memoization (Top-Down DP) Approach
Intuition:
The recursive solution recalculates solutions for overlapping subproblems, leading to inefficiencies. By storing previously calculated results in a 2D array, we can optimize the recursive solution using memoization.
Steps:
- Use a 2D array
memowherememo[i][j]indicates whethers1[i:]ands2[j:]can interleave intos3[i+j:]. - Follow the same logic as the recursive approach, but store results in
memobefore making recursive calls, and checkmemobefore calculating new results.
Code:
- Time Complexity: O(m * n), since each state
(i, j)is computed only once. - Space Complexity: O(m * n) for memoization storage.
3. Iterative Dynamic Programming Approach
Intuition:
Transforming the recursive approach into an iterative form using a 2D boolean array can avoid the function call overhead.
Steps:
- Create a 2D boolean array
dpwheredp[i][j]is true ifs1[0:i]ands2[0:j]can interleave intos3[0:i+j]. - Initialize
dp[0][0]to true because empty strings interleave to make an empty string. - Iterate over
s1ands2and filldpbased on previous results. - Return
dp[m][n].
Code:
- Time Complexity: O(m * n), where m is the length of
s1and n is the length ofs2. - Space Complexity: O(m * n) for the DP table. However, this can also be optimized to O(n) by using a rolling array technique.