Given two strings s1 and s2, write a function that will print all the interleavings of the given two strings.
Here interleaving string is a string which has the same order that of individual strings.
In the below example, we can see that ‘A’ will always comes before ‘B’ and ‘C’ will always comes before ‘D’
Example
INPUT
s1 = “AB”
s2 = “CD”
OUTPUT
ABCD, ACBD, ACDB, CABD, CADB, CDAB
Algorithm
1. First, fix the first character in ‘s1’ and recursively find other characters
ie, for above example, we get
ABCD, ACBD, ACDB
2. Now, fix the first character in “s2” and recursivley find other characters
ie, for above example, we get
CABD, CADB, CDAB
#include <bits/stdc++.h>
using namespace std;
//Recursive function to print all the IL strings
void printIlStrings(char *s1, char *s2, char *res, int m,
int n, int i)
{
//If all the characters of s1 and s2 are in res, then print res
if (m==0 && n==0)
{
cout<<res<<endl;
}
//If there are chars in m, then include the first char in res
//and recur for other char in m
if (m != 0)
{
res[i] = s1[0];
printIlStrings(s1 + 1, s2, res, m-1, n, i+1);
}
//If there are chars in n, then include the first char in res
//and recur for other char in n
if (n != 0)
{
res[i] = s2[0];
printIlStrings(s1, s2+1, res, m, n-1, i+1);
}
}
//In this function we will initailixe res string and will call recursive function
void printIls (char *s1, char *s2, int m, int n)
{
//Initializing res string
char *res = new char[m+n+1];
//setting the terminator of the res string
res[m+n] = '\0';
printIlStrings(s1, s2, res, m, n, 0);
// free memory to avoid memory leak
free(res);
}
int main()
{
char s1[] = "AB";
char s2[] = "CD";
printIls (s1, s2, strlen(s1), strlen(s2));
return 0;
}