Print all interleavings of two strings

Given two strings, write code to print all inter-leavings of these strings.  For example: if the two strings are  “AB” and “12”, then the output should be:

    AB12
    A1B2
    A12B
    1AB2
    1A2B
    12AB

Note that the order of characters in the individual strings are not changed in the output.

Solution:

The logic for this is simple, we will use one character from each string and put it in the result. This function requires recursion. The main function to print interleavings will just allocate memory for the result string (If there are m & n characters in the 2 strings, then number of characters in the resultant string will be m+n)

void printInterleaving(char* a, char* b)
 {
    // allocate memory to result string
     char * res = new char[strlen(a) + strlen(b) + 1];
    // Call the recursive function to print interleavings
     printInter(a, b, res, 0);
    // Delete memory allocated to result string
     delete[] res;
 }

The recursive function is where the actual code will be.

void printInter(char* a, char* b, char* res, int i=0)
{
    // If both the strings are empty then print the result.
    if(*a == '\0' && *b == '\0')
    {
        res[i] = '\0';
        cout<<"\n"<<res;
    }
    // Add first character of string a to result
    if(*a != '\0')
    {
        res[i] = *a;
        printInter(a+1, b, res, i+1);
    }
    // Add first character of string b to result
    if(*b != '\0')
    {
        res[i] = *b;
        printInter(a, b+1, res, i+1);
    }
}

Time Complexity: O(m!.n!). This is the total number of inter-leavings for the 2 strings.