Problem Statement
This is a question from one of the interview experiences. The statement, "Given three strings A, B and C find if C is an interleaving of A and B." Interleaving is defined as below:
A string C is said to be an interleaving of two strings A and B if C contains a sub sequence of A and B such that the relative order of characters in A and in B are preserved in C.
For e.g. :
A - ABCD
B - BACDX
C - ABACDXBCD
The Idea - Interleaving Strings
Here I am not giving any solution which is less than O(M*N) solution where M is the length of the shortest string among A and B...

Read More