Check if given string is interleaving of two other given strings

Given three strings, return true if third string is interleaving of first and second string. i.e., it is formed from all characters of first and second string and order of characters is preserved.


 

For example,


ACDB is interleaving of AB and CD

ADEBCF is interleaving of ABC and DEF

ACBCD is interleaving of ABC and CD

ACDABC is interleaving of ABC and ACD

 


 

We can easily solve this problem using recursion.

C++

Download   Run Code

Output:

Given string is interleaving of X and Y

The time complexity of above solution is O(m + n) where m and n are the lengths of X and Y. Auxiliary space used by the program is O(1).
 

The problem with the above solution is that it doesn’t handle duplicates. Suppose X = “ABC” and Y = “ACD”, then above solution will return false for string S = “ACDABC”. The reason is that if the current character of S matches with current character of both X and Y, the solution will always pair S with X and do not check if solution can be formed by pairing S with Y or not.

We can easily handle duplicates by pairing S with both X and Y and recusively check if the solution can be formed by either of them or not.

C++

Download   Run Code

Output:

Given string is interleaving of X and Y

The worst case time complexity of above solution is exponential and worst case happens when all characters of X and Y are same. We can use Dynamic Programming to reduce worst case time complexity to O(mn) (DP will take O(mn) extra space).

The DP solution is discussed below –

C++

Download   Run Code

Output:

Given string is interleaving of X and Y

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz