97. Interleaving String
Problem Description
Given three strings s1
, s2
, and s3
, we need to determine if s3
can be constructed by interleaving characters from s1
and s2
. The interleaving of s1
and s2
should create a sequence where characters from s1
and s2
are alternated, but maintain their relative order from the original strings. There can be more than one character from either string coming in sequence, but overall, the characters from s1
and s2
should come in the exact order they appear in their respective strings.
For example, if s1 = "abc"
and s2 = "def"
, then s3 = "adbcef"
would be a valid interleaving. However, s3 = "abcdef"
or s3 = "badcfe"
would not be valid interleavings, because the relative ordering of the characters from s1
and s2
isn't respected in s3
.
Intuition
The intuition for solving this problem lies in dynamic programming. We can imagine forming s3
character by character, making choices at each step of taking the next character from either s1
or s2
. If at any point, the characters from s1
or s2
do not match the current character in s3
, we cannot proceed further by that route.
The key insight for the solution is to construct a table (or array) that represents whether it is possible to form the prefix s3[0...k]
from prefixes of s1
and s2
. We initialize an array f
of length n+1
(where n
is the length of s2
), which will help us track if s3
can be formed up to the j
-th character of s2
. We start by assuming that an empty s3
can be formed without any characters from either string (which is always true).
We then iterate over all characters in both s1
and s2
, updating the array at each step. The condition f[j] &= s1[i - 1] == s3[k]
checks if we can form the string by taking the next character from s1
, while the condition f[j] |= f[j - 1] and s2[j - 1] == s3[k]
checks if we can form the string by taking the next character from s2
.
This way, we fill up the table iteratively, making sure at every step that we satisfy the condition of interleaving without violating the original order in the given strings. If, by the end of the iteration, we find that f[n]
is True
, it means that we can form s3
by interleaving s1
and s2
. Otherwise, we cannot.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution uses dynamic programming, a method that solves problems by breaking them down into simpler subproblems and stores the results of those subproblems to avoid redundant computations.
Here's a step-by-step breakdown of the algorithm:
-
We begin by defining the lengths of
s1
ands2
asm
andn
, respectively. Immediately, we check if the length ofs3
is equal to the sum of the lengths ofs1
ands2
(m + n
). If not,s3
cannot be an interleaving ofs1
ands2
, and we returnFalse
. -
We then create an array
f
of lengthn+1
.f[j]
will hold a boolean value indicating whethers3[0...i+j-1]
is a valid interleaving ofs1[0...i-1]
ands2[0...j-1]
. Here is a critical observation:f[0]
is initialized toTrue
because an empty string is considered an interleaving of two other empty strings by default. -
We iterate through both strings
s1
ands2
using two nested loops, one for indexi
ranging from0
tom
, and another for indexj
ranging from0
ton
. Each iteration represents an attempt to match the character ins3
at the current combined indexk = i + j - 1
. -
For each pair
(i, j)
, ifi
is not zero, we updatef[j]
to keep track of whethers3[k]
can still match with the character ins1[i - 1]
. This is indicated by the operationf[j] &= s1[i - 1] == s3[k]
. -
Similarly, if
j
is not zero, we updatef[j]
to see ifs3[k]
can match with the characters2[j - 1]
, while also taking into account the value off[j - 1]
, which indicates whether the interleaving was possible without considering the current character ofs2
. This happens with the operationf[j] |= f[j - 1] and s2[j - 1] == s3[k]
. -
After both loops terminate, we return the value of
f[n]
. Iff[n]
isTrue
, it means thats3
can be formed by interleavings1
ands2
. Otherwise, it means that it is not possible.
The above steps summarize the dynamic programming approach to solving the interleaving string problem. It's worth noting that the space complexity is optimized to O(n)
since we are only using a single one-dimensional array to store the results.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a simple example to illustrate the solution approach. Consider the following strings:
s1 = "ax"
s2 = "by"
s3 = "abxy"
Here's how we'd walk through the algorithm:
-
First, we determine the lengths of
s1
(lengthm = 2
), ands2
(lengthn = 2
). The length ofs3
is 4, which is equal tom + n
(2 + 2), so it's possible fors3
to be an interleaving ofs1
ands2
. -
We create an array
f
withn+1
elements, which includes the initial condition (f[0] = True
). Initiallyf = [True, False, False]
. -
We begin iterating over the strings:
-
For
i = 0
(considering an empty string fors1
):- For
j = 0
,f[0]
remainsTrue
because an empty string can interleave with another empty string to form an empty string. - For
j = 1
, sinces2[0]
('b'
) matchess3[0]
('a'
),f[1]
remainsFalse
. - For
j = 2
, sinces2[1]
('y'
) does not matchs3[1]
('b'
),f[2]
remainsFalse
. After checking,f = [True, False, False]
.
- For
-
For
i = 1
(considering the first character ofs1
):- For
j = 0
,s1[0]
('a'
) matchess3[0]
('a'
), sof[0]
remainsTrue
. - For
j = 1
, sinces2[0]
('b'
) matchess3[1]
('b'
),f[1]
is updated toTrue
. - For
j = 2
, sinces2[1]
('y'
) does not matchs3[2]
('x'
),f[2]
remainsFalse
. After checking,f = [True, True, False]
.
- For
-
For
i = 2
(considering the second character ofs1
):- For
j = 0
,s1[1]
('x'
) matchess3[2]
('x'
), sof[0]
remainsTrue
. - For
j = 1
, sinces2[0]
('b'
) does not matchs3[3]
('y'
),f[1]
remainsTrue
. - For
j = 2
,s2[1]
('y'
) matchess3[3]
('y'
), and sincef[1]
isTrue
,f[2]
is updated toTrue
. After checking,f = [True, True, True]
.
- For
-
Once we have completed our iterations, the final
f
array is[True, True, True]
. -
At the end, we examine the value of
f[n]
, which in this case isTrue
, indicating thats3
can indeed be formed by interleavings1
ands2
.
This completes the example walkthrough, showing that given the strings s1 = "ax"
, s2 = "by"
, and s3 = "abxy"
, s3
is a valid interleaving of s1
and s2
using the described dynamic programming approach.
Solution Implementation
1class Solution:
2 def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
3 # Get the lengths of the input strings.
4 len_s1, len_s2 = len(s1), len(s2)
5
6 # If the combined length of s1 and s2 is not equal to the length of s3,
7 # it is impossible for s3 to be an interleaving of s1 and s2.
8 if len_s1 + len_s2 != len(s3):
9 return False
10
11 # Initialize a list to keep track of the possibility of interleaving up to each position.
12 # The +1 accounts for the empty substring. True implies that the interleaving is possible.
13 dp = [True] + [False] * len_s2
14
15 # Check if substrings of s1 can interleave with an empty s2 to form corresponding
16 # substrings of s3.
17 for i in range(len_s1 + 1):
18 for j in range(len_s2 + 1):
19 # k is the current index in s3 that we want to match.
20 k = i + j - 1
21 # If we are not at the first row, check if previous character in s1 matches with
22 # current character in s3. Use "&=" to modify the existing dp[j] value.
23 if i:
24 dp[j] &= s1[i - 1] == s3[k]
25 # If we are not at the first column, check if the above cell or the left cell
26 # can lead to an interleaving. Use "|=" to incorporate this new possibility.
27 if j:
28 dp[j] |= dp[j - 1] and s2[j - 1] == s3[k]
29
30 # The last element in the dp array contains the answer.
31 return dp[len_s2]
32
33# The function isInterleave returns True if s3 is an interleaving of s1 and s2, otherwise False.
34
1class Solution {
2 public boolean isInterleave(String s1, String s2, String s3) {
3
4 // Get the lengths of the strings
5 int m = s1.length(), n = s2.length();
6
7 // If the combined length of s1 and s2 does not equal the length of s3, return false
8 if (m + n != s3.length()) {
9 return false;
10 }
11
12 // Create a boolean array to keep track of the interleavings
13 boolean[] dp = new boolean[n + 1];
14 dp[0] = true;
15
16 // Iterate over each character of both s1 and s2
17 for (int i = 0; i <= m; ++i) {
18 for (int j = 0; j <= n; ++j) {
19
20 // Index k for matching characters in s3
21 int k = i + j - 1;
22
23 // If there are remaining characters in s1, check if they match s3's characters
24 if (i > 0) {
25 dp[j] &= s1.charAt(i - 1) == s3.charAt(k);
26 }
27
28 // If there are remaining characters in s2, check if they match s3's characters
29 if (j > 0) {
30 dp[j] |= (dp[j - 1] & (s2.charAt(j - 1) == s3.charAt(k)));
31 }
32 }
33 }
34
35 // Return whether it's possible to interleave s1 and s2 to get s3
36 return dp[n];
37 }
38}
39
1class Solution {
2public:
3 bool isInterleave(string s1, string s2, string s3) {
4 int length1 = s1.size(), length2 = s2.size();
5
6 // If the sum of lengths of s1 and s2 is not equal to length of s3,
7 // then s3 cannot be formed by interleaving s1 and s2
8 if (length1 + length2 != s3.size()) {
9 return false;
10 }
11
12 // dp array to hold the computed values; indicates if s3 up to a point
13 // is an interleaving of s1 and s2 up to certain points
14 bool dp[length2 + 1];
15
16 // Initialize the dp array to false
17 memset(dp, false, sizeof(dp));
18
19 // Base case: empty strings are considered interleaving
20 dp[0] = true;
21
22 // Iterate over characters in s1 and s2
23 for (int i = 0; i <= length1; ++i) {
24 for (int j = 0; j <= length2; ++j) {
25 // Calculate the corresponding index in s3
26 int indexS3 = i + j - 1;
27
28 // If we can take a character from s1 and it matches the corresponding character in s3,
29 // we maintain the value of dp[j] (continue to be true or false based on previous value)
30 if (i > 0) {
31 dp[j] = dp[j] && (s1[i - 1] == s3[indexS3]);
32 }
33
34 // If we can take a character from s2 and it matches the corresponding character in s3,
35 // we update the value of dp[j] to be true if it's either true already or
36 // if previous element in dp array was true (indicating a valid interleave up to that point)
37 if (j > 0) {
38 dp[j] = dp[j] || (s2[j - 1] == s3[indexS3] && dp[j - 1]);
39 }
40 }
41 }
42
43 // Return the last element in the dp array,
44 // which represents whether the whole s3 is an interleaving of s1 and s2
45 return dp[length2];
46 }
47};
48
1function isInterleave(s1: string, s2: string, s3: string): boolean {
2 const s1Length = s1.length;
3 const s2Length = s2.length;
4
5 // If the lengths of s1 and s2 together don't add up to the length of s3, they can't interleave to form s3.
6 if (s1Length + s2Length !== s3.length) {
7 return false;
8 }
9
10 // Initialize an array to hold the interim results of the dynamic programming solution.
11 // dp[i] will hold the truth value of whether s1 up to i characters can interleave with s2 up to j characters to form s3 up to i+j characters.
12 const dp: boolean[] = new Array(s2Length + 1).fill(false);
13
14 // Initialize the first value to true as an empty string is considered an interleave of two other empty strings.
15 dp[0] = true;
16
17 // Iterate over each character in s1 and s2 to build up the solution in dp.
18 for (let i = 0; i <= s1Length; ++i) {
19 for (let j = 0; j <= s2Length; ++j) {
20 // Calculate the corresponding index in s3.
21 const s3Index = i + j - 1;
22
23 // If we are not at the start of s1, determine if the current character of s1 is equal to the current character of s3
24 // and whether the result up to the previous character of s1 was true.
25 if (i > 0) {
26 dp[j] = dp[j] && s1[i - 1] === s3[s3Index];
27 }
28
29 // If we are not at the start of s2, determine if the current character of s2 is equal to the current character of s3
30 // and whether the result up to the previous character of s2 was true.
31 if (j > 0) {
32 dp[j] = dp[j] || (dp[j - 1] && s2[j - 1] === s3[s3Index]);
33 }
34 }
35 }
36
37 // The final result would be if s1 up to its full length can interleave with s2 up to its full length to form s3.
38 return dp[s2Length];
39}
40
Time and Space Complexity
The given Python code provides a solution to determine if a string s3
is formed by the interleaving of two other strings s1
and s2
. Let's analyze both the time complexity and space complexity of the code.
Time Complexity
The outer loop in the code runs m + 1
times, where m
is the length of s1
. Within this loop, there's an inner loop that runs n + 1
times, where n
is the length of s2
. However, observe that for each outer iteration, the inner loop starts at 1 (since j
ranges from 0 to n
), so the combined iterations for the inner loop are actually m * (n + 1)
.
Each iteration of the inner loop consists of constant time checks and assignment operations, so its time complexity is O(1)
. Thus, the total time complexity for the double loop structure is O(m * (n + 1))
. Simplifying, this is equivalent to O(m * n)
since the addition of a constant 1
does not change the order of growth.
Therefore, the overall time complexity of the code is O(m * n)
.
Space Complexity
Space complexity considers the additional space used by the algorithm excluding the input sizes. In the code, a one-dimensional Boolean array f
is initialized with n + 1
elements. The space usage of this array dominates the space complexity. There is no other data structure that grows with the input size. Thus, the space complexity is based on the size of f
, which is O(n)
.
To summarize:
- Time complexity:
O(m * n)
- Space complexity:
O(n)
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!