資料結構
網路
關係資料庫管理系統 (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 次瀏覽
