Print all interleavings of two given strings

Question

Given two strings str1 and str2, write a function that prints all interleavings of the given two strings. You may assume that all characters in both strings are different

Example:

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

The idea comes from Ray Toal:

The base case is when one of the two strings are empty:

interleave(s1, "") = {s1}
interleave("", s2) = {s2}

Notice the order of the arguments doesn't really matter, because

interleave("ab", "12") = {"ab12", "a1b2", "1ab2", "a12b", "1a2b", "12ab"} = interleave("12", "ab")

So since the order doesn't matter we'll look at recursing on the length of the first string.

Okay so let's see how one case leads to the next. I'll just use a concrete example, and you can generalize this to real code.

interleave("", "abc") = {"abc"} interleave("1", "abc") = {"1abc",
"a1bc", "ab1c", "abc1"} interleave("12", "abc") = {"12abc", "1a2bc",
"1ab2c", "1abc2", "a12bc", "a1b2c", "a1bc2", "ab12c", "ab1c2" "abc12"}

So everytime we added a character to the first string, we formed the new result set by adding the new character to all possible positions in the old result set. Let's look at exactly how we formed the third result above from the second. How did each element in the second result turn into elements in the third result when we added the "2"?

"1abc" => "12abc", "1a2bc", "1ab2c", "1abc2" "a1bc" => "a12bc",
"a1b2c", "a1bc2" "ab1c" => "ab12c", "ab1c2" "abc1" => "abc2"

Now look at things this way:

"1abc" => {1 w | w = interleave("2", "abc")} "a1bc" => {a1 w | w =
interleave("2", "bc")} "ab1c" => {ab1 w | w = interleave("2", "c")}
"abc1" => {abc1 w | w = interleave("2", "")}

The following is my code building on top of the above idea. Can anyone help me verify it?

void interleaving(const string& s2, string result, int start, int depth)
{
 if(depth == s2.size())
 cout << result << endl;
 else
 {
 for(int i = start; i <= result.size(); ++i)
 {
 result.insert(i, 1, s2[depth]);
 interleaving(s2, result, i+1, depth+1);
 result.erase(i, 1);
 }
 }
}
int main()
{
 string s1("");
 string s2("12");
 string result(s1);
 interleaving(s2, result, 0, 0); 
 system("pause");
 return 0;
}

There is another much more beautiful solution for this problem comes from an unknown friend akash01:

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

• Loki Astari: There is a standard function to do this: std::next_permutation()
• Fihop: @LokiAstari, thanks very much. If it was an interview question and ask you to write the code by yourself, can you help me check it?
• William Morris: Why not test it with the examples you gave in the question? Also, does it have to be recursive? Your last question used recursion too... (perhaps you should be learning Haskell).
• Fihop: @WilliamMorris, I've tested a lot of cases including the examples given in the question. It seems it's right. I'm doing practice in recursive algorithm. :-)
• Seg Fault: @LokiAstari Given that the characters from either input string occur in the same order in the output as in the respective input, how does next_permutation help?

Answer 1

Your algorithm is correct, as you explained. However, I didn't find the code easy to understand.

Staying within the spirit of your solution, I've cleaned it up a bit:

• Renamed s2 → s1 (because s2 coming first is confusing), result → s2.
• Renamed depth → i1, start → i2 to emphasize their relationship with s1 and s2.
• Swapped the order of the last two parameters for parallelism.
• Provided defaults for the last two parameters to make main() prettier.
• Eliminated the variable i, because using i2 directly is clearer.
• Used an early return to reduce a level of indentation.

Simultaneously tracking all of those substitutions is tricky, but here is the result:

void interleaving(const string& s1, string s2, int i1=0, int i2=0)
{
 if (i1 == s1.size())
 {
 cout << s2 << endl;
 return;
 }
 // Transfer the first character of s1 into s2
 // anywhere after the last previously inserted
 // character from s1.
 for ( ; i2 <= s2.size(); i2++)
 {
 s2.insert(i2, 1, s1[i1]);
 interleaving(s1, s2, i1 + 1, i2 + 1);
 s2.erase(i2, 1); // Undo the insert() above
 }
}

Since passing the second parameter by value would cause it to be copied unnecessarily on each recursive call, you might want to change it to be passed by reference instead.

static void interleaving_helper(const string& s1, string &s2, int i1, int i2)
{
 if (i1 == s1.size())
 {
 cout << s2 << endl;
 return;
 }
 for ( ; i2 <= s2.size(); i2++)
 {
 s2.insert(i2, 1, s1[i1]);
 interleaving_helper(s1, s2, i1 + 1, i2 + 1);
 s2.erase(i2, 1); // Undo the insert above
 }
}
void interleaving(const string& s1, string s2, int i1=0, int i2=0)
{
 interleaving_helper(s1, s2, i1, i2);
}

Answer 2

For comparison, here's a "pure" recursive solution that resembles the solution by akash01. It isn't implemented efficiently, but it illustrates the elegance of recursion and is a good starting point.

void interleave(const std::string s1, const std::string s2, const std::string result="") {
 if (s1.empty() && s2.empty()) {
 std::cout << result << std::endl;
 return;
 }
 if (!s1.empty()) {
 interleave(s1.substr(1), s2, result + s1[0]);
 }
 if (!s2.empty()) {
 interleave(s1, s2.substr(1), result + s2[0]);
 }
}

That pure solution involves a lot of copying, so here's an adaptation to make it more idiomatic C++:

/* Helper function */
static void interleave(std::string::const_iterator s1, std::string::const_iterator end1,
 std::string::const_iterator s2, std::string::const_iterator end2,
 const std::string &result = "") {
 if (s1 == end1 && s2 == end2) {
 std::cout << result << std::endl;
 return;
 }
 if (s1 != end1) {
 interleave(s1 + 1, end1, s2, end2, result + *s1);
 }
 if (s2 != end2) {
 interleave(s1, end1, s2 + 1, end2, result + *s2);
 }
}
void interleave(const std::string &s1, const std::string &s2) {
 interleave(s1.begin(), s1.end(), s2.begin(), s2.end());
}

You might compromise purity for a further performance gain by using result as a mutable buffer:

static void interleave(std::string::const_iterator s1, std::string::const_iterator end1,
 std::string::const_iterator s2, std::string::const_iterator end2,
 std::string &result) {
 if (s1 == end1 && s2 == end2) {
 std::cout << result << std::endl;
 return;
 }
 if (s1 != end1) {
 interleave(s1 + 1, end1, s2, end2, result.append(1, *s1));
 result.pop_back();
 }
 if (s2 != end2) {
 interleave(s1, end1, s2 + 1, end2, result.append(1, *s2));
 result.pop_back();
 }
}
void interleave(const std::string &s1, const std::string &s2) {
 std::string buffer;
 buffer.reserve(s1.length() + s2.length()); // optional
 interleave(s1.begin(), s1.end(), s2.begin(), s2.end(), buffer);
}