Menukar rentetan yang diberikan kepada T, dengan menggantikan aksara antara rentetan beberapa kali

Menukar rentetan bermakna kita perlu menjadikannya sama dengan rentetan yang diberikan berdasarkan syarat yang diberikan. Dalam soalan ini, kita diberikan tatasusunan yang terdiri daripada rentetan "arr" dan rentetan "T" bersaiz "M". Tugas kami adalah untuk menyemak sama ada semua rentetan yang terdapat dalam tatasusunan boleh dibuat sama dengan yang diberikan dengan mengalih keluar sebarang aksara daripada rentetan ( arr[i] ) tatasusunan dan memasukkan aksara itu ke dalam mana-mana indeks rentetan lain Rentetan T A rentetan daripada tatasusunan yang sama ( arr[j] ). Kita boleh melakukan ini seberapa banyak yang kita suka. Mengembalikan "YA" jika semua rentetan dalam tatasusunan boleh dibuat sama dengan rentetan 'T', jika tidak mengembalikan "TIDAK".

Contoh

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

Output 1: YES

Arahan

Salah satu cara yang mungkin untuk menjadikan semua rentetan dalam tatasusunan sama dengan rentetan T adalah seperti berikut -

• Padamkan aksara daripada rentetan arr[1] ("wxxy") pada indeks 2 dan masukkannya ke dalam rentetan arr[2] ("wyzz") pada indeks 1. Kemudian ia kelihatan seperti: ["wxyz","wxy","wxyzz"]

• Padamkan aksara daripada rentetan arr[2] ("wxyzz") pada indeks 3 dan masukkannya ke dalam rentetan arr[1] ("wxy") pada indeks 3. Kemudian ia kelihatan seperti: ["wxyz","wxyz","wxyz"].

Selepas melakukan langkah di atas, kita boleh membuat semua rentetan dalam tatasusunan sama dengan rentetan T. Jadi jawapannya "YA".

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

Output 2: NO

Arahan

Terdapat 3 rentetan dalam tatasusunan, 2 daripadanya sama dengan rentetan T, tetapi rentetan dengan nombor indeks 1 adalah berbeza. Ia mengandungi aksara berbeza yang bukan sebahagian daripada rentetan T. Tidak mungkin untuk menjadikan semua rentetan dalam tatasusunan rentetan T. Oleh itu, jawapannya ialah "TIDAK".

Kaedah: Gunakan Hashmap

Kami telah melihat contoh rentetan yang diberikan di atas, mari kita beralih ke kaedah -

Kami mempunyai dua pemerhatian seperti berikut -

• Oleh kerana kita mesti menjadikan semua rentetan dalam tatasusunan sama dengan rentetan T, supaya semua aksara setiap rentetan dalam tatasusunan mesti muncul dalam rentetan T. Dengan kata lain, tidak ada watak yang berbeza. Jika tidak, kita tidak boleh memenuhi syarat.

• Selepas kita mengira kekerapan kejadian aksara untuk semua rentetan dalam tatasusunan, kekerapan kejadian setiap aksara mestilah sama dengan saiz tatasusunan "N".

Berdasarkan pemerhatian di atas, kami mempunyai dua syarat untuk diperiksa.

• Peta cincang rentetan tatasusunan saiz "freqArr" adalah sama dengan peta cincang "freqT" rentetan "T". sebagai

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

• Setiap aksara rentetan T hendaklah muncul dalam setiap rentetan tatasusunan. Setiap aksara rentetan T harus mempunyai kiraan kekerapan "N" dalam rentetan tatasusunan. As-

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

Kita boleh menggunakan pencincangan untuk menyelesaikan masalah ini kerana kita perlu mengira kekerapan aksara dalam rentetan tatasusunan dan rentetan T.

Contoh

Mari lihat kod kaedah di atas untuk pemahaman yang lebih baik -

// 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;
}

Output

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

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(M + N*L)

Kerumitan ruang kod di atas ialah O(M)

Di mana M ialah saiz rentetan T, N ialah saiz tatasusunan, dan L ialah rentetan terpanjang yang terdapat dalam tatasusunan.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program yang menukar rentetan yang diberikan kepada T dengan menggantikan aksara antara rentetan seberapa banyak yang perlu. Kami melaksanakan kaedah pencincangan kerana kami perlu menyimpan frekuensi. Dalam kaedah ini, kami terutamanya menyemak dua syarat, jika semua syarat dipenuhi, ini bermakna kami dapat menukar semua rentetan dalam tatasusunan ke dalam rentetan yang sama dengan rentetan T.

Atas ialah kandungan terperinci Menukar rentetan yang diberikan kepada T, dengan menggantikan aksara antara rentetan beberapa kali. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!