Imprimir todos los intercalados de dos strings dadas

Dadas dos strings str1 y str2, escriba una función que imprima todos los intercalados de las dos strings dadas. Puede suponer que todos los caracteres en ambas strings son diferentes 
. Ejemplo: 

Input: str1 = "AB",  str2 = "CD"
Output:
    ABCD
    ACBD
    ACDB
    CABD
    CADB
    CDAB

Input: str1 = "AB",  str2 = "C"
Output:
    ABC
    ACB
    CAB

Una string intercalada de dos strings dadas conserva el orden de los caracteres en strings individuales. Por ejemplo, en todos los intercalados del primer ejemplo anterior, ‘A’ viene antes que ‘B’ y ‘C’ viene antes que ‘D’.

Sea m la longitud de str1 y n la longitud de str2. Supongamos que todos los caracteres en str1 y str2 son diferentes. Sea count(m, n) el conteo de todas las strings intercaladas en tales strings. El valor de count(m, n) se puede escribir de la siguiente manera. 

     count(m, n) = count(m-1, n) + count(m, n-1)
     count(1, 0) = 1 and count(0, 1) = 1

Para imprimir todos los intercalados, primero podemos corregir el primer carácter de str1[0..m-1] en la string de salida y llamar recursivamente a str1[ 1 ..m-1] y str2[0..n-1]. Y luego podemos corregir el primer carácter de str2[0..n-1] y llamar recursivamente a str1[0..m-1] y str2[ 1 ..n-1]. Gracias a akash01 por proporcionar la siguiente implementación de C. 

// C program to print all interleavings of given two strings
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// The main function that recursively prints all interleavings.
// The variable iStr is used to store all interleavings (or
// output strings) one by one. 
// i is used to pass next available place in iStr
void printIlsRecur (char *str1, char *str2, char *iStr, int m,
                    int n, int i)
{
    // Base case: If all characters of str1 and str2 have been
    // included in output string, then print the output string
    if (m==0 && n==0)
        printf("%s\n", iStr) ;
 
    // If some characters of str1 are left to be included, then
    // include the  first character from the remaining characters
    // and recur for rest
    if (m != 0)
    {
        iStr[i] = str1[0];
        printIlsRecur (str1 + 1, str2, iStr, m-1, n, i+1);
    }
 
    // If some characters of str2 are left to be included, then
    // include the  first character from the remaining characters
    // and recur for rest
    if (n != 0)
    {
        iStr[i] = str2[0];
        printIlsRecur(str1, str2+1, iStr, m, n-1, i+1);
    }
}
 
// Allocates memory for output string and uses printIlsRecur()
// for printing all interleavings
void printIls (char *str1, char *str2, int m, int n)
{
   // allocate memory for the output string
   char *iStr= (char*)malloc((m+n+1)*sizeof(char));
 
   // Set the terminator for the output string
   iStr[m+n] = '\0';
 
   // print all interleavings using printIlsRecur()
   printIlsRecur (str1, str2, iStr, m, n, 0);
 
   // free memory to avoid memory leak
   free(iStr);
}
 
// Driver program to test above functions
int main()
{
    char str1[] = "AB";
    char str2[] = "CD";
    printIls (str1, str2, strlen(str1), strlen(str2));
    return 0;
}

// C++ program to print all interleavings of given two strings
#include <bits/stdc++.h>
using namespace std;
 
// The main function that recursively prints all interleavings.
// The variable iStr is used to store all interleavings (or
// output strings) one by one.
// i is used to pass next available place in iStr
void printIlsRecur (char *str1, char *str2, char *iStr, int m,
                    int n, int i)
{
    // Base case: If all characters of str1 and str2 have been
    // included in output string, then print the output string
    if (m == 0 && n == 0)
        cout << iStr << endl ;
 
    // If some characters of str1 are left to be included, then
    // include the first character from the remaining characters
    // and recur for rest
    if (m != 0)
    {
        iStr[i] = str1[0];
        printIlsRecur (str1 + 1, str2, iStr, m - 1, n, i + 1);
    }
 
    // If some characters of str2 are left to be included, then
    // include the first character from the remaining characters
    // and recur for rest
    if (n != 0)
    {
        iStr[i] = str2[0];
        printIlsRecur(str1, str2 + 1, iStr, m, n - 1, i + 1);
    }
}
 
// Allocates memory for output string and uses printIlsRecur()
// for printing all interleavings
void printIls (char *str1, char *str2, int m, int n)
{
    // allocate memory for the output string
    char *iStr= new char[((m + n + 1)*sizeof(char))];
     
    // Set the terminator for the output string
    iStr[m + n] = '\0';
     
    // print all interleavings using printIlsRecur()
    printIlsRecur (str1, str2, iStr, m, n, 0);
     
    // free memory to avoid memory leak
    free(iStr);
}
 
// Driver code
int main()
{
    char str1[] = "AB";
    char str2[] = "CD";
    printIls (str1, str2, strlen(str1), strlen(str2));
    return 0;
}
 
// This is code is contributed by rathbhupendra

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    /*
     * This methods prints interleaving string of two
     * strings
     * @param s1  String 1
     * @param i   current index of s1
     * @param s2  String 2
     * @param j  Current index of s2
     * @param asf String containing interleaving string of
     *     s1 and s2
     *
     */
    static void printInterLeaving(String s1, int i,
                                  String s2, int j,
                                  String asf)
    {
        if (i == s1.length() && j == s2.length()) {
            System.out.println(asf);
        }
 
        // Either we will start with string 1
        if (i < s1.length())
            printInterLeaving(s1, i + 1, s2, j,
                              asf + s1.charAt(i));
        // Or with string 2
        if (j < s2.length())
            printInterLeaving(s1, i, s2, j + 1,
                              asf + s2.charAt(j));
    }
 
    /*
     * Main function executed by JVM
     * @param args String array
     */
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
 
        String s1 = "AB"; // String 1
        String s2 = "CD"; // String 2
       
        printInterLeaving(s1, 0, s2, 0, "");
    }
}
 
/* Code by mahi_07 */

# Python program to print all interleavings of given two strings
 
# Utility function
def toString(List):
    return "".join(List)
 
# The main function that recursively prints all interleavings.
# The variable iStr is used to store all interleavings (or output
# strings) one by one.
# i is used to pass next available place in iStr
def printIlsRecur(str1, str2, iStr, m, n, i):
 
    # Base case: If all characters of str1 and str2 have been
    # included in output string, then print the output string
    if m==0 and n==0:
        print (toString(iStr))
 
    # If some characters of str1 are left to be included, then
    # include the first character from the remaining characters
    # and recur for rest
    if m != 0:
        iStr[i] = str1[0]
        printIlsRecur(str1[1:], str2, iStr, m-1, n, i+1)
 
    # If some characters of str2 are left to be included, then
    # include the first character from the remaining characters
    # and recur for rest
    if n != 0:
        iStr[i] = str2[0]
        printIlsRecur(str1, str2[1:], iStr, m, n-1, i+1)
 
# Allocates memory for output string and uses printIlsRecur()
# for printing all interleavings
def printIls(str1, str2, m, n):
    iStr = [''] * (m+n)
 
    # print all interleavings using printIlsRecur()
    printIlsRecur(str1, str2, iStr, m, n, 0)
 
# Driver program to test the above function
str1 = "AB"
str2 = "CD"
printIls(str1, str2, len(str1), len(str2))
 
# This code is contributed by Bhavya Jain

Producción:

ABCD
ACBD
ACDB
CABD
CADB
CDAB

Complejidad temporal: O(2 ^ (m+n))