將給定的字串轉換為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中文網其他相關文章！