Convertit la chaîne donnée en T, en remplaçant les caractères entre les chaînes un certain nombre de fois

Convertir une chaîne signifie que nous devons la rendre identique à la chaîne donnée en fonction de la condition donnée. Dans cette question, on nous donne un tableau composé d'une chaîne "arr" et d'une chaîne "T" de taille "M". Notre tâche est de vérifier si toutes les chaînes présentes dans le tableau peuvent être rendues identiques à celle donnée en supprimant n'importe quel caractère de la chaîne ( arr[i] ) du tableau et en insérant ce caractère dans n'importe quel index d'une autre chaîne. String T String du même tableau ( arr[j] ). Nous pouvons faire cela autant de fois que nous le souhaitons. Renvoie "OUI" si toutes les chaînes du tableau peuvent être rendues identiques à la chaîne "T", sinon renvoie "NON".

Exemple

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

Output 1: YES

Instructions

L'une des façons possibles de rendre toutes les chaînes d'un tableau identiques à la chaîne T est la suivante -

• Supprimez le caractère de la chaîne arr[1] ("wxxy") à l'index 2 et insérez-le dans la chaîne arr[2] ("wyzz") à l'index 1. Ensuite, cela ressemble à : ["wxyz","wxy","wxyzz"]

• Supprimez le caractère de la chaîne arr[2] ("wxyzz") à l'index 3 et insérez-le dans la chaîne arr[1] ("wxy") à l'index 3. Cela ressemble alors à : ["wxyz","wxyz","wxyz"].

Après avoir effectué les étapes ci-dessus, nous pouvons rendre toutes les chaînes du tableau identiques à la chaîne T. La réponse est donc « OUI ».

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

Output 2: NO

Instructions

Il y a 3 chaînes dans le tableau, dont 2 sont identiques à la chaîne T, mais la chaîne avec le numéro d'index 1 est différente. Il contient différents caractères qui ne font pas partie de la chaîne T. Il n'est pas possible de faire de toutes les chaînes du tableau une chaîne T. La réponse est donc « NON ».

Méthode : utiliser Hashmap

Nous avons vu l'exemple ci-dessus avec la chaîne donnée, passons à la méthode -

Nous avons deux observations comme suit -

• Parce que nous devons rendre toutes les chaînes du tableau identiques à la chaîne T, de sorte que tous les caractères de chaque chaîne du tableau doivent apparaître dans la chaîne T. En d’autres termes, il n’y a pas de personnages différents. Sinon, nous ne pouvons pas remplir les conditions.

• Après avoir calculé la fréquence d'occurrence des caractères pour toutes les chaînes du tableau, la fréquence d'occurrence de chaque caractère doit être égale à la taille du tableau "N".

Sur la base des observations ci-dessus, nous avons deux conditions à vérifier.

• La carte de hachage des chaînes du tableau de taille "freqArr" est égale à la carte de hachage "freqT" de la chaîne "T". comme

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

• Chaque caractère de la chaîne T doit apparaître dans chaque chaîne du tableau. Chaque caractère de la chaîne T doit avoir une fréquence de « N » dans la chaîne du tableau. Comme-

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

Nous pouvons utiliser le hachage pour résoudre ce problème car nous devons calculer la fréquence des caractères dans la chaîne du tableau et la chaîne T.

Exemple

Voyons le code de la méthode ci-dessus pour une meilleure compréhension -

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

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(M + N*L)

La complexité spatiale du code ci-dessus est O(M)

Où M est la taille de la chaîne T, N est la taille du tableau et L est la chaîne la plus longue présente dans le tableau.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme qui convertit une chaîne donnée en T en remplaçant les caractères entre les chaînes autant de fois que nécessaire. Nous avons mis en place une méthode de hachage car nous devions stocker les fréquences. Dans cette méthode, nous vérifions principalement deux conditions, si toutes les conditions sont remplies, cela signifie que nous sommes capables de convertir toutes les chaînes du tableau en la même chaîne que la chaîne T.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!