检查给定字符串是否可以由其他两个字符串或它们的排列组成

---

字符串是由字符、数字连续组成的序列。它甚至可能包含特殊字符。一个字符串可以由多个子字符串组成，也称为单词。

字符串的排列是另一个由同一组字符组成的字符串，可能以不同的顺序排列。它基本上可以被认为是字符串字母的重新排序。例如，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）的字符数组的评估，因此第二种方法被认为优于第一种方法。第二种方法将多项式时间方法的时间复杂度降低到接近多项式的近似值。