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.
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
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments