Konvertiert die angegebene Zeichenfolge in T, indem Zeichen zwischen Zeichenfolgen beliebig oft ersetzt werden

Das Konvertieren einer Zeichenfolge bedeutet, dass wir sie basierend auf der angegebenen Bedingung mit der angegebenen Zeichenfolge übereinstimmen müssen. In dieser Frage erhalten wir ein Array bestehend aus der Zeichenfolge „arr“ und der Zeichenfolge „T“ der Größe „M“. Unsere Aufgabe besteht darin, zu prüfen, ob alle im Array vorhandenen Zeichenfolgen mit der angegebenen identisch gemacht werden können, indem ein beliebiges Zeichen aus der Zeichenfolge ( arr[i] ) des Arrays entfernt und dieses Zeichen in einen beliebigen Index einer anderen Zeichenfolge eingefügt wird. Zeichenfolge T Eine Zeichenfolge des gleichen Arrays ( arr[j] ). Wir können dies so oft tun, wie wir möchten. Gibt „JA“ zurück, wenn alle Zeichenfolgen im Array mit der Zeichenfolge „T“ identisch gemacht werden können, andernfalls wird „NEIN“ zurückgegeben.

Beispiel

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

Output 1: YES

Anleitung

Eine der möglichen Möglichkeiten, alle Zeichenfolgen in einem Array mit der Zeichenfolge T identisch zu machen, ist wie folgt:

• Löschen Sie das Zeichen aus der Zeichenfolge arr[1] („wxxy“) an Index 2 und fügen Sie es in die Zeichenfolge arr[2] („wyzz“) an Index 1 ein. Dann sieht es so aus: ["wxyz", "wxy", "wxyzz"]

• Löschen Sie das Zeichen aus der Zeichenfolge arr[2] („wxyzz“) an Index 3 und fügen Sie es in die Zeichenfolge arr[1] („wxy“) an Index 3 ein. Dann sieht es so aus: ["wxyz", "wxyz", "wxyz"].

Nachdem wir die obigen Schritte ausgeführt haben, können wir alle Zeichenfolgen im Array mit der Zeichenfolge T identisch machen. Die Antwort lautet also „JA“.

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

Output 2: NO

Anleitung

Das Array enthält 3 Zeichenfolgen, von denen 2 mit der Zeichenfolge T identisch sind, die Zeichenfolge mit der Indexnummer 1 jedoch unterschiedlich ist. Es enthält verschiedene Zeichen, die nicht Teil der Zeichenfolge T sind. Es ist nicht möglich, alle Zeichenfolgen im Array zu einer Zeichenfolge T zu machen. Daher lautet die Antwort „NEIN“.

Methode: Hashmap verwenden

Wir haben das obige Beispiel mit der angegebenen Zeichenfolge gesehen. Kommen wir nun zur Methode -

Wir haben folgende zwei Beobachtungen -

• Weil wir alle Zeichenfolgen im Array mit Zeichenfolge T identisch machen müssen, sodass alle Zeichen jeder Zeichenfolge im Array in Zeichenfolge T erscheinen müssen. Mit anderen Worten, es gibt keine unterschiedlichen Charaktere. Andernfalls können wir die Bedingungen nicht erfüllen.

• Nachdem wir die Häufigkeit des Auftretens von Zeichen für alle Zeichenfolgen im Array berechnet haben, muss die Häufigkeit des Auftretens jedes Zeichens gleich der Größe des Arrays „N“ sein.

Basierend auf den obigen Beobachtungen müssen wir zwei Bedingungen überprüfen.

• Die Hash-Map von Strings des Größenarrays „freqArr“ ist gleich der Hash-Map „freqT“ des Strings „T“. als

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

• Jedes Zeichen der Zeichenfolge T sollte in jeder Zeichenfolge des Arrays erscheinen. Jedes Zeichen der Zeichenfolge T sollte eine Häufigkeitsanzahl von „N“ in der Array-Zeichenfolge haben. Als-

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

Wir können Hashing verwenden, um dieses Problem zu lösen, da wir die Häufigkeit der Zeichen im Array string und string T berechnen müssen.

Beispiel

Sehen wir uns zum besseren Verständnis den Code der oben genannten Methode an -

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

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(M + N*L)

Die räumliche Komplexität des obigen Codes beträgt O(M)

Wobei M die Größe der Zeichenfolge T ist, N die Größe des Arrays und L die längste im Array vorhandene Zeichenfolge ist.

Fazit

In diesem Tutorial haben wir ein Programm implementiert, das eine bestimmte Zeichenfolge in ein T umwandelt, indem es Zeichen zwischen den Zeichenfolgen so oft wie nötig ersetzt. Wir haben eine Hashing-Methode implementiert, weil wir die Häufigkeiten speichern mussten. Bei dieser Methode prüfen wir hauptsächlich zwei Bedingungen. Wenn alle Bedingungen erfüllt sind, bedeutet dies, dass wir alle Zeichenfolgen im Array in dieselbe Zeichenfolge wie die Zeichenfolge T konvertieren können.

Das obige ist der detaillierte Inhalt vonKonvertiert die angegebene Zeichenfolge in T, indem Zeichen zwischen Zeichenfolgen beliebig oft ersetzt werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!