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