## 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.

- The first character of A matches with the front character of C
- Eventually the base condition of recursion will arrive and the method will return back.

### Source

Here is the relevant part of the source code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
private static boolean canBeConstructed(String s1, String s2, String s3) { if (s1.length() + s2.length() != s3.length()) return false; if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0) { return true; } boolean result1 = false; if (s1.length() > 0 && (s1.charAt(0) == s3.charAt(0))) result1 = canBeConstructed(s1.substring(1), s2, s3.substring(1)); boolean result2 = false; if (!result1 && s2.length() > 0 && (s2.charAt(0) == s3.charAt(0))) result2 = canBeConstructed(s1, s2.substring(1), s3.substring(1)); return result1 || result2; } |

### 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
- Invocation
**A(bcd), B(ade), C(badcde)** - 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
- Invocation
**A(cd), B(ade), C(adcde)** - 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.

- Invocation
- Return value received in previous step is
**true**(as we are taking an OR from both the results)

- Invocation
- Return value received in previous step is
**true**

- Invocation
- Return value received here is
**true**

- Invocation
- Return value received here is
**true**

- Invocation
- Return value here is
**true**

- Invocation
- 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).