檢查給定字串是否可以由其他兩個字串或它們的排列組成

---

字串是由字元、數字連續組成的序列。它甚至可能包含特殊字元。一個字串可以由多個子字串組成，也稱為單詞。

字串的排列是另一個由同一組字元組成的字串，可能以不同的順序排列。它基本上可以被認為是字串字母的重新排序。例如，abcd 和 badc 是同一個字串的排列。

示例

示例 1：str：“Permutation”

arr：{“repuio”，“mat”，“mtatn”，“mutate”}

輸出：Yes

輸入字串“Permutation”可以由索引為 0 和 2 的字串對組成，即“repuio”和“mtatn”，它們可以重新排列以形成等效字串。

這個問題可以使用 C++ 中的以下兩種方法解決：

• 使用排序

• 使用計數排序

方法 1：使用排序

提供了一個字串輸入陣列。在使用 for 迴圈對字串進行巢狀迭代期間，從輸入陣列中捕獲一對字串。如果輸入字串的排序版本以及生成的字串對的排列計算結果為相同的字串，則進行比較。

語法

sort()

C++ 中的 sort() 方法用於對給定字串進行升序或降序排序。

sort(str.begin() , str.end())

引數

str.begin() - 字串的開頭。

str.end() - 字串的結尾。

演算法

• 步驟 1 - 接受一個輸入字串和一個字串陣列。

• 步驟 2 - 使用 C++ 中的 sort() 方法對字串進行初始排序。

• 步驟 3 - 執行字串的巢狀迴圈迭代，其中一次訪問一對字串，使用指標 i 和 j。每次迴圈 j 從索引 i 開始，一直持續到字串的長度。同時訪問索引 i 和 j 處的兩個字串並連線起來。

• 步驟 4 - 然後使用 sort() 方法再次對連線的字串進行排序。

• 步驟 5 - 然後比較連線的字串和輸入排序字串。如果它們等效，則返回 true。否則，如果沒有任何對匹配，則返回 false。

示例

以下 C++ 程式碼片段用於將示例字串和字串陣列作為輸入，並找出是否可以使用陣列中的任何字串對生成示例字串：

//including the required libraries
#include <bits/stdc++.h>
using namespace std;

//check if string can be formed by permutations of two strings
bool permutation( string str,vector<string> arr) {
   int size = arr.size();

   //sorting the given string
   sort(str.begin(), str.end());

   //extracting two strings at a time
   for (int i = 0; i < size - 1; i++) {
      for (int j = i + 1; j < size; j++) {

         //concatenate the pair of string
         string concat = arr[i] + arr[j];

         // Sort the resultant string
         sort(concat.begin(), concat.end());

         //comparing if the order of characters in both strings are same
         if (concat.compare(str) == 0) {

            //if equal
            return true;
         }
      }
   }

   //no such combination exists
   return false;
}
int main(){

   //declaring the input string
   string str = "tutorials";

   //array of strings
   vector<string> arr{ "trils", "outa", "ginc", "abc" };
   bool res = permutation(str,arr);
   if(res)
      cout << "Yes, the string can be formed by permutation of two other strings";
   else
      cout << "No, the string can't be formed by permutation of two other strings";
   return 0;
}

輸出

Yes, the string can be formed by permutation of two other strings

方法 2：使用計數排序

提供了一個字串輸入陣列和一個示例字串。使用計數排序對示例字串進行排序。在使用 for 迴圈對字串進行巢狀迭代期間，從輸入陣列中捕獲一對字串。然後，生成連線的字串，也使用計數排序進行排序。如果字串以及生成的字串對的排列計算結果為相同的字串，則進行比較。

計數排序

可以維護一個大小為 26 個字元的陣列，以儲存字串中每個字元出現的頻率。最終，按升序提取字元以獲得排序後的字串。

演算法

• 步驟 1 - 接受一個輸入字串和一個字串陣列。

• 步驟 2 - 使用計數排序演算法對字串進行初始排序。

• 步驟 3 - 執行字串的巢狀迴圈迭代，其中一次訪問一對字串，使用指標 i 和 j。

• 步驟 4 - 每次迴圈 j 從索引 i 開始，一直持續到字串的長度。同時訪問索引 i 和 j 處的兩個字串並連線起來。

• 步驟 5 - 然後使用計數排序機制再次對連線的字串進行排序。

• 步驟 6 - 然後比較連線的字串和輸入排序字串。如果它們等效，則返回 true。否則，如果沒有任何對匹配，則返回 false。

示例

//including the required libraries
#include <bits/stdc++.h>
using namespace std;

// Function to sort the given string
// using counting sort
void countsort(string& str){

   //declaring the numbr of characters
   int numchar = 26;

   //string length
   int len = str.length();

   //initialise the count of array
   int count[numchar] = { 0 };

   //declaring an index param
   int idx = 0;

   //traversing the string
   for (int i = 0; i < len; i++) {
      char ch = str[i] ;
      count[ch - 'a']++;
   }

   //increasing order insertion
   for (int i = 0; i < numchar; i++) {
      int j = 0;
      for (j=0; j < count[i];j++) {
         str[idx] = i + 'a';
         idx++;
      }
   }
}

//check if string can be formed by permutations of two strings
bool permutation( string str,vector<string> arr){
   int size = arr.size();

   //sorting the given string
   countsort(str);

   //extracting two strings at a time
   for (int i = 0; i < size - 1; i++) {
      for (int j = i + 1; j < size; j++) {

         //concatenate the pair of string
         string concat = arr[i] + arr[j];

         // Sort the resultant string
         countsort(concat);

         //comparing if the order of characters in both strings are same
         if (concat.compare(str) == 0) {

            //if equal
            return true;
         }
      }
   }

   //no such combination exists
   return false;
}
int main(){

   //declaring the input string
   string str = "tutorials";

   //array of strings
   vector<string> arr{ "trils", "outa", "ginc", "abc" };
   printf("\nString 2:\n");
   for (int i = 0; i <4 ; i++){
      cout<<arr[i]<<endl;
   }
   bool res = permutation(str,arr);
   if(res)
      cout << "Yes, the string can be formed by permutation of two other strings";
   else
      cout << "No, the string can't be formed by permutation of two other strings";
   return 0;
}

輸出

String 2:
trils
outa
ginc
abc
Yes, the string can be formed by permutation of two other strings

結論

由於計數排序機制僅考慮有限大小（即 26）的字元陣列的評估，因此第二種方法被認為優於第一種方法。第二種方法將多項式時間方法的時間複雜度降低到接近多項式的近似值。