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

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 3.67 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
MessiCR7
Guest

If the question asks us to ensure there are no repetitions, what’s a good way of doing that?

Mystix
Guest

This solution is wrong. See this http://javabypatel.blogspot.com/2016/03/print-all-interleaving-of-given-two-strings.html.

It should give 20 different strings for ABC and ACB. But yours is giving only 10.
Output is ABCACB
ABACCB
ABACCB
ABACBC
AABCCB
AABCCB
AABCBC
AACBCB
AACBBC
AACBBC
AABCCB
AABCCB
AABCBC
AACBCB
AACBBC
AACBBC
ACABCB
ACABBC
ACABBC
ACBABC