Interleaving of two strings

Question

I have written this recursive code to find all interleaves of two strings, where the order of strings are preserved. For example:

s1="abc" s2="1"
a1bc
ab1c
abc1

You can see that the order of s1 and s2 is preserved.

// Interleave_Two_Strings.cpp : Defines the entry point for the console application. //

#include "stdafx.h"
#include "iostream"
#include "vector"
#include "string"
using namespace std;
class Solution {
public:
    vector<string> res;
    void helper(string s1, string s2,string s3) {
        if (s1 == "" && s2 == "") {
            if(std::find(res.begin(),res.end(),s3)==res.end())
                res.push_back(s3);
            return;
        }
        if (s2 == "") {
            res.push_back(s3+s1);
            return;
        }
        if (s1 == "") {
            res.push_back(s3 + s2);
            return;
        }
        for (int i = 0; i < s1.size(); i++) {
            for (int j = 0; j < s2.size(); j++) {
                helper(s1.substr(i + 1, s1.size()),s2.substr(j+1,s2.size()),s3+s1.substr(0, i+1)+s2.substr(0,j+1));
            }
        }
    }
    void interleave(string s1, string s2) {
        if (s1==""|| s2=="")
            return;
        for (int i = 0; i < s2.size(); i++) {
            helper(s1, s2.substr(0, i+1),"");
        }
        res.pop_back();
    }
};
int main()
{
    Solution s;
    s.interleave("abc", "123");
    return 0;
}

Answer 1

Here are some observations that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Isolate platform-specific code

If you must have stdafx.h, consider wrapping it so that the code is portable:

#ifdef WINDOWS
#include "stdafx.h"
#endif

Make sure you have all required #includes

The code uses std::find but doesn't #include <algorithm>.

Be careful with signed and unsigned

In the current helper and interleave routines, the loop integer i and j are both signed int values, but they're being compared with size_t quantities (which are unsigned) s1.size() and s2.size(). Better would be to declare them all as size_t.

Understand how #include works

On most platforms, the difference between #include "iostream" and #include <iostream> is that the former looks first in the current directory. So for system files such as iostream, you should really use #include <iostream> instead. See this question for more details.

Rethink your algorithm

The result of this program is somewhat peculiar. If we run it with ab and 12 we get this:

a1b, ab1, a1b2, a12b

This seems to be incorrect because the first two don't include all of the input letters and none of the combinations begin with 1 and the combination ab12 is not listed. If this is intended, then it's just the description that is faulty. If not, it's a bug and should be fixed.

Hide internal object details

If the sole purpose for the object is to create a vector of interleaved strings, it seems to me that interleave should actually return a vector of strings rather than keeping it as an internal object. The helper function should also be made private if it's not intended to be used externally. Finally, if the object has no data, as per this recommendation, the member functions can all be declared static so that no object instantiation need exist to use the function.

Pass by const reference where practical

All of the std::string arguments are being passed by value, which cause the argument to be duplicated. Better would be to make each of them const std::string & because they are not modified and don't need to be duplicated.

Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.