Print all interleavings of given two strings


StringViews 1864

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;
    
}

Try It

 

Translate ยป