将给定的字符串转换为T，通过任意次数替换字符串之间的字符

转换字符串意味着我们必须根据给定条件将其与给定字符串相同。在这个问题中，我们给出了一个由字符串“arr”和大小为“M”的字符串“T”组成的数组。我们的任务是检查是否可以通过从数组的字符串（ arr[i] ）中删除任何字符并将该字符插入到另一个字符串的任何索引中来使数组中存在的所有字符串与给定的字符串 T 相同数组的字符串 ( arr[j] )。我们可以这样做任意多次。如果可以使数组中的所有字符串与字符串‘T’相同，则返回“YES”，否则返回“NO”。

示例

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

Output 1: YES

说明

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

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

• 删除索引 3 处字符串 arr[2] (“wxyzz”) 的字符并将其插入到索引 3 处字符串 arr[1] (“wxy”) 处。然后它看起来像： [ “ wxyz”、“wxyz”、“wxyz”]。

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

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

Output 2: NO

说明

数组中存在 3 个字符串，其中 2 个与字符串 T 相同，但索引号为 1 的字符串不相同。它包含不属于字符串T的不同字符。不可能使数组中的所有字符串都成为字符串T。因此，答案为“NO”。

方法：使用Hashmap

我们已经看到了上面给定字符串的示例，让我们转向该方法 -

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

• 因为我们必须让数组中的所有字符串都与字符串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.

我们可以使用哈希来解决这个问题，因为我们需要计算数组 string 和字符串 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 相同的字符串。

以上是将给定的字符串转换为T，通过任意次数替换字符串之间的字符的详细内容。更多信息请关注PHP中文网其他相关文章！