2つの文字列で形成できる文字列を印刷

Question

私は以下の問題を解決しようとしています。しかし、正しい解決策を見つけることができませんでした

xyzとabcという2つの文字列があるとします。これらの2つの文字列で形成できるすべての文字列を探します。 1つの制約は、各文字列の文字列が同じままであることです。

例：

xyabzc - Valid 

xabcyz - Valid 

abcxyz - Valid 

xyzacb - Invalid. (b cannot come before c) 

は、私は新しい文字列に以下、

連結文字列の両方を試してみました。文字列のすべての置換を取得し、上記の制約に従わないものを削除しました。私はこれが非常に曖昧であることを知っていますが、それが私が思いついた唯一の解決策です。

より良いアプローチを提案してください。

Answer 1

この問題は、再帰によって非常に簡単に解決できます。各ステップで、最初の文字列の文字または2番目の文字列の文字を追加できます。

C++コード -

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

出力 -

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