C++ 转换给定的字符串成为T，可以任意次数地替换字符串之间的字符

转换字符串意味着根据给定条件使其与给定字符串相同。在这个问题中，我们给出了一个字符串数组’arr’和大小为’M’的字符串’T’。我们的任务是检查是否可以通过从数组的字符串（arr[i]）中删除任何字符并将该字符插入数组的其他字符串（arr[j]）的任意索引来使数组中的所有字符串都与给定字符串T相同。我们可以任意多次地进行此操作。如果能够使数组中的所有字符串与字符串’T’相同，则返回”YES”，否则返回”NO”。

示例

Input 1: arr = [ “wxyz”, “wxxy”, “wyzz” ], T = “wxyz”

Output 1: YES

解释

使数组中的所有字符串与字符串T相同的一种可能方法如下:

• 在字符串arr[1]（“wxxy”）的索引2处删除字符，并插入到字符串arr[2]（“wyzz”）的索引1处。然后它看起来像：[“wxyz”，“wxy”，“wxyzz”]

• 在字符串arr[2]（“wxyzz”）的索引3处删除字符，并插入到字符串arr[1]（“wxy”）的索引3处。然后它看起来像：[“wxyz”，“wxyz”，“wxyz”]。

执行上述步骤后，我们能够使数组中的所有字符串与字符串T相同。因此答案是“YES”。

Input 2: arr = [ “rts”, “rtw”, “rts” ], T = “rts”

Output 2: NO

说明

数组中有3个字符串，其中有2个与字符串T相同，但索引编号为1的字符串不同。它包含一个不是字符串T的不同字符。无法使数组中的所有字符串都变为字符串T。因此，答案是“NO”。

方法：使用哈希映射

我们已经看到了上述给定字符串的示例，接下来我们来看一下方法-

我们有两个观察结果，如下所示-

• 因为我们需要使数组中的所有字符串都与字符串T相同，所以数组中每个字符串的每个字符都必须存在于字符串T中。换句话说，没有不同的字符存在。否则，我们将无法满足条件。

• 当我们完成计算数组中所有字符串的字符频率计数时，每个字符的频率计数必须等于数组的大小N。

根据上述观察，我们有两个条件需要检查。

• 数组的哈希映射‘freqArr’的大小等于字符串‘T’的哈希映射‘freqT’的大小。

freqArr.size() == freqT.size()

• 字符串T的每个字符应出现在数组的每个字符串中。数组字符串中每个字符在字符串T中的频率计数应为’N’。如-

freqArr.find(T[i]) == freqArr.end() and 
freqArr[T[i]] != freqT[T[i]]*N.

我们可以使用哈希来解决这个问题，因为我们需要计算数组字符串和字符串T中字符的频率。

示例

让我们看一下上述方法的代码，以便更好地理解。

// Program to convert all strings to T
#include <bits/stdc++.h>
using namespace std;
string covertStringIntoT( int N, string arr[], string T){
   map< char,int > freqT; //to store the frequency of each character of string T
   int len = T.size(); //getting the size of the string T 

   //traverse the string T to store the frequency of the characters
   for( int i=0; i<len; i++){
      freqT[T[i]]++;
   }
   map< char,int > freqArr; //to store the frequency of each chracter of strings 

   // of Array.
   //traverse the strings of Array to store the frequency of the characters
   for( int i=0; i<N; i++){
      for(int j=0;j<arr[i].size(); j++){
         freqArr[arr[i][j]]++;
      }
   }

   // Check the condition one
   if(freqT.size() != freqArr.size()){
      return "NO";
   }    

   //check condition two while trversing the string T
   for( int i=0; i<len; i++){
      if(freqArr.find(T[i]) == freqArr.end() || freqArr[T[i]] != freqT[T[i]]*N ){
         return "NO";
      }
   }
   return "YES";
}
int main() {    
   string T = "wxyz"; // given string
   string arr[] = {"wxyz", "wxyy", "wxzz"}; // given array of strings
   int N = sizeof(arr) / sizeof(arr[0]); //getting the size of the array of string 

   // calling the function 'convertStringIntoT' to convert all strings of the 

   // array into string T
   string result = covertStringIntoT( N, arr, T);
   if(result == "YES"){
      cout<< result << ", it is possible to make all the strings of the array as string T";
   }
   else{
      cout<< result << ", it is not possible to make all the strings of the array as string T"; 
   }
   return 0;
}

输出

YES, it is possible to make all the strings of the array as string T

时间和空间复杂度

以上代码的时间复杂度为O(M + N*L)

以上代码的空间复杂度为O(M)

其中M是字符串T的大小，N是数组的大小，L是数组中最长的字符串的长度。

结论

在本教程中，我们实现了一个程序，通过替换字符串之间的字符任意次数，将给定的字符串转换为T。我们采用了哈希的方法来存储频率。在这个方法中，我们主要要检查两个条件，如果所有条件都满足，那么我们就能把数组中所有的字符串转换成T。