数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学将给定的字符串转换为 T，方法是在字符串之间替换任意次数的字符。
转换字符串意味着我们必须根据给定的条件使字符串与给定字符串相同。在这个问题中，我们给定一个大小为 'N' 的字符串数组 '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 不相关的不同字符。不可能使数组的所有字符串都与字符串 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 相同的字符串。
70 次浏览
