# Solution to find Interleaving of Strings

## Introduction

This post is an enhancement over one of the previous posts where the task was to find if a given string C is an interleaving of strings A and B. To know more about the problem description, please visit the previous post

## Solution

The previous solution is a iterative solution which requires lot of space. Here we will discuss a recursive solution. Hopefully with small code foot print. Before we jump into the code, let us understand the idea behind the solution.

Here are the example Strings A, B and C

• A -> abcd
• B -> ade
• C -> abadcde

### The recursive algorithm

The task is to check if C can be constructed from A and B while maintaining the relative ordering of the characters in A and B. Here is the initial draft of our algorithm

• If the sum of lengths of A and B is not equal to the length of C, then return false because its impossible to interleave two strings and get a resultant string if the results length is not equal to the sum of lengths of the contributing strings
• If all the strings are exhausted then return true. This means our algorithm ended up and we didn’t fail in the earlier steps.
• Initialize two boolean variables R1 and R2 to false.
• Now, we need to check for the front character of all the strings and there can be three cases
• The first character of A matches with the front character of C
• In this case, we can recursively make the same check by removing the first character of A and C, keeping B intact.
• Store the result (true/false) in a variable R1
• If the first character of B matches with the front character of C
• In this case, we can recursively make the same check by removing the first character of B and C, keeping A intact.
• Store the result (true/false) in another variable R2
• Neither the first character of A nor B match with the first  character of C
• In this just return R1 || R2 because R1 and R2 are initialized to false.
• Eventually the base condition of recursion will arrive and the method will return back.

### Source

Here is the relevant part of the source code

### Dry Run

Let us try to dry run the algorithm for few steps and let that sink in.

Steps

• We invoke the canBeConstructed method with A(abcd), B(ade) and C(abadcde)
• The first two conditions won’t fulfill. The first character of A matches with the first character of C. So, invoke the method recursively after removing the first characters of A and C
• Again, the first two conditions won’t fulfill. Also, the first character of A matches with the first character of C. So, invoke the method recursively after removing the first characters from A and C
• This time, the first characters of A and C won’t match, but the first character of B and C do match. So, invoke the method recursively after removing the first characters from B and C
• Invocation A(cd), B(de), C(dcde)
• This time, the first character of B and C match, so invoke the method after stripping the first character of B and C
• Invocation A(cd), B(e), C(cde)
• The first character of A and C match, so strip them and proceed with next invocation
• Invocation A(d), B(e), C(de)
• The first character of A and C match, so strip and proceed with next invocation
• Invocation A(), B(e), C(e)
• This time the character of B and C matches and the next invocation is with three empty strings.
• The next invocation will return true because the lengths of the arguments are zero.
• Return value received in previous step is true (as we are taking an OR from both the results)
• Return value received in previous step is true
• Return value received here is true
• Return value received here is true
• Return value here is true
• Return value here is true, and the method now returns to the caller.

Above is the recursion stack and this is how the algorithm will execute.

## Analysis

Now, this is a recursive function, which means it will consume some space for the recursion stack. The space is proportional to the length of the longest String that is length of C if this is going to result in success. In case of failures, it might break out early.

So we can safely say that the space complexity is O(L), where L is the length of the resultant string.

Time complexity, can be argued in the same way.

You can write the recurrence as T(L) = 2T(L-1) + O(1)  which is exponential in runtime. In practice, this algorithm finishes much faster than that. T(L) = O(2^L).