CODEWITHSUNDEEP
stringalgorithmdata-structures
Amarnath
Amarnath

Reputation: 8865

Print strings that can be formed with two strings

I am trying to solve the below problem. But could not come up with a correct solution

Given two strings say xyz and abc. Find all the strings that can be formed with these two strings. One constraint is that the sequence of characters in each string should remain the same.

Examples:

xyabzc - Valid

xabcyz - Valid

abcxyz - Valid

xyzacb - Invalid. (b cannot come before c)

I tried the following,

Concatenated both the strings into a new string. Got all the permutations of the string and removed the one's that are not following the above constraint. I know this is very vague but that's the only solution I came up.

Please suggest a better approach.

Upvotes: 2

Views: 218

Answers (1)

Vedang Mehta
Vedang Mehta

Reputation: 2254

You can solve this problem very easily with recursion. In each step, you can either add a character from the first string or a character from the second string.

C++ code -

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string s1, s2;  //Input strings
vector <string> v;  //To store resultant strings

void merge_strings(int i,int j,string res)
{
        if(i == s1.length() && j == s2.length())
                v.push_back(res);
        if(i < s1.length())
                merge_strings(i + 1,j,res + s1[i]);
        if(j < s2.length())
                merge_strings(i,j + 1,res + s2[j]);
}

int main()
{
        s1 = "abc";
        s2 = "xyz";
        merge_strings(0,0,"");
        for(string s : v)
                cout << s << endl;
        return 0;
}

Output -

abcxyz
abxcyz
abxycz
abxyzc
axbcyz
axbycz
axbyzc
axybcz
axybzc
axyzbc
xabcyz
xabycz
xabyzc
xaybcz
xaybzc
xayzbc
xyabcz
xyabzc
xyazbc
xyzabc

Upvotes: 8

Related Questions