Find all interleavings of given strings

Find all interleavings of given strings that can be formed from all the characters of first and second string where order of characters is preserved.


 

For example, interleavings of string ABC and ACB are


ACBABC
AABCBC
ACABCB
ABCACB
AACBBC
ABACCB
ACABBC
ABACBC
AACBCB
AABCCB

 

 
We can easily solve this problem using recursion. The idea is to append first or last character of X and Y in the result one by one and recurse for remaining substring.


Input: X[1..m], Y[1..n]

fun(X, m, Y, n) = fun(X, m-1, Y, n) + X[m]
                  fun(X, m, Y, n-1) + Y[n]

fun(X, 0, Y, n) = Y[n]    // X is empty
fun(X, m, Y, 0) = X[m]    // Y is empty

 
Below is C++ and Java implementation of the idea:

C++

Download   Run Code

Java

Download   Run Code

Output:

ACBABC
AABCBC
ACABCB
ABCACB
AACBBC
ABACCB
ACABBC
ABACBC
AACBCB
AABCCB

 
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 🙂
 


Get great deals at Amazon




Leave a Reply

Notify of
avatar
wpDiscuz