## 97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = `"aabcc"`,
s2 = `"dbbca"`,

When s3 = `"aadbbcbcac"`, return true.
When s3 = `"aadbbbaccc"`, return false.

b'
\n\n

## Summary

\n

We need to determine whether a given string can be formed by interleaving the other two strings.

\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

The most basic idea is to find every string possible by all interleavings of the two given strings( and ).\nIn order to implement this method, we are using recursion. We start by taking the current character of the\nfirst string() and then appending all possible interleavings of the remaining portion of the first string() and the second string()\nand comparing each result formed with the required interleaved string(). Similarly, we choose one character from the second\nstring() and form all the interleavings with the remaining portion of and to check if the required string can be formed.

\n

For implementing the recursive function, we make the function call recursively as\n in which we have chosen the current character from and then make another function call , in which the current character of is chosen. Here, refers to that portion(interleaved) of and which has already been processed. If anyone of these calls return the result as , it means that atleast one interleaving gives the required result . The recursive calls end when both the strings and have been fully processed.

\n

Let\'s look at a small example to see how the execution proceeds.

\n
`s1="abc"\ns2="bcd"\ns3="abcbdc"\n`
\n

Firstly we choose \'a\' of s1 as the processed part i.e. res and call the recursive function considering the new strings as s1="bc",\ns2="bcd", s3="abcbdc". When this function returns a result, we again call the recursive function but with the new strings as s1="abc", s2="cd", s3="abcbdc"

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . is the length of and is the length of .

\n
• \n
• \n

Space complexity : . The size of stack for recursive calls can go upto .

\n
• \n
\n
\n

#### Approach #2 Recursion with memoization [Accepted]

\n

Algorithm

\n

In the recursive approach discussed above, we are considering every possible string formed by interleaving the two given\nstrings. But, there will be cases encountered in which, the same portion of and would have been processed already\nbut in different orders(permutations). But irrespective of the order of processing, if the resultant string formed till now\nis matching with the required string(), the final result is dependent only on the remaining portions of and , but\nnot on the already processed portion. Thus, the recursive approach leads to redundant computations.

\n

This redundancy can be removed by making use of memoization along with recursion. For this, we maitain 3 pointers \n which correspond to the index of the current character of respectively. Also, we maintain a 2-d memo array to keep a track of the substrings processed so far. stores a 1/0 or -1 depending on\n whether the current portion of strings i.e. upto index for and upto index for s2 has already been evaluated. Again, we start by selecting the current character of (pointed by \$\$i\$). If it matches the current character\n of (pointed by ), we include it in the processed string and call the same function recurively as:\n \n

\n

Thus, here we have called the function by incrementing the pointers and since the portion of strings upto those indices\n has already been processed. Similarly, we choose one character from the second string and continue. The recursive function\n ends when either of the two strings or has been fully processed. If, let\'s say, the string has been fully processed,\n we directly compare the remaining portion of with the remaining portion of . When the backtrack occurs from the recursive\n calls, we store the value returned by the recursive functions in the memoization array memo appropriatelys so that when it is encountered the next time, the recursive function won\'t be called, but the memoization array itself will return the previous generated result.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . is the length of and is the length of .

\n
• \n
• \n

Space complexity : . The size of stack for recursive calls can go upto .

\n
• \n
\n
\n

#### Approach #3 Using 2-d Dynamic Programming [Accepted]

\n

Algorithm

\n

The recursive approach discussed in above solution included a character from one of the strings or in the resultant\ninterleaved string and called a recursive function to check whether the remaining portions of and can be interleaved\nto form the remaining portion of . In the current approach, we\n look at the same problem the other way around. Here, we include one character from or and check whether the\n resultant string formed so far by one particular interleaving of the the current prefix of and form a prefix of .

\n

Thus, this approach relies on the fact that the in order to determine whether a substring\n of (upto index ), can be formed by interleaving strings and upto indices and respectively, solely depends\n on the characters of and upto indices and only and not on the characters coming afterwards.

\n

To implement this method, we\'ll make use of a 2-d boolean array . In this array implies if it is possible to\n obtain a substring of length which is a prefix of by some interleaving of prefixes of strings and having\n lengths and respectively. For filling in the entry of , we need to consider two cases:

\n
\n
1. \n

The character\n just included i.e. either at index of or at index of doesn\'t match the character at index of , where .\n In this case, the resultant string formed using some interleaving of prefixes of and can never result in a prefix of length in . Thus, we enter at the character .

\n
2. \n
3. \n

The character\n just included i.e. either at index of or at index of matches the character at index of , where .\nNow, if the character just included(say ) which matches the character at index of , is the character at index of , we need to keep at the last position in the resultant interleaved string formed so far. Thus, in order to use string and upto indices and to form a resultant string of length which is a prefix of , we need to ensure that the strings and upto indices and respectively obey the same property.

\n
4. \n
\n

Similarly, if we just included the character of , which matches with the character of , we need to ensure that the strings and upto indices and also obey the same\nproperty to enter a at .

\n

This can be made clear with the following example:

\n
`s1="aabcc"\ns2="dbbca"\ns3="aadbbcbcac"\n`
\n\n

!?!../Documents/97_Interleaving.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . dp array of size is filled.

\n
• \n
• \n

Space complexity : . 2-d DP of size is required. and are the lengths of strings and repectively.

\n
• \n
\n
\n

#### Approach #4 Using 1-d Dynamic Programming [Accepted]:

\n

Algorithm

\n

This approach is the same as the previous approach except that we have used only 1-d array to store the results of the\n prefixes of the strings processed so far. Instead of maintaining a 2-d array, we can maintain a 1-d array only and update the\n array\'s element when needed using and the previous value of .

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . dp array of size is filled times.

\n
• \n
• \n

Space complexity : . is the length of the string .

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'