Vérifiez si toutes les chaînes d'un tableau peuvent être rendues identiques en échangeant des caractères

Dans cet article, nous explorerons le problème de vérifier si toutes les chaînes d'un tableau sont identiques en échangeant les caractères. Nous comprendrons d’abord l’énoncé du problème, puis étudierons des moyens simples et efficaces de résoudre le problème, ainsi que leurs algorithmes respectifs et leur complexité temporelle. Enfin, nous implémenterons la solution en C++.

Énoncé du problème

Étant donné un tableau de chaînes, déterminez si toutes les chaînes peuvent être rendues identiques en échangeant les caractères.

Méthode naïve

Le moyen le plus simple consiste à trier les caractères de chaque chaîne du tableau, puis à comparer chaque chaîne triée à la chaîne triée suivante. Si toutes les chaînes triées sont égales, cela signifie que toutes les chaînes peuvent être rendues égales en échangeant les caractères.

Algorithme (naïf)

• Triez les caractères de chaque chaîne du tableau.

• Comparez chaque chaîne triée à la chaîne triée suivante.

• Renvoie vrai si toutes les chaînes triées sont égales ; sinon, renvoie faux.

Code C++ (simple)

Exemple

#include <iostream>
#include <vector>
#include <algorithm>

bool canBeMadeSame(std::vector<std::string> &strArray) {
   for (auto &str : strArray) {
      std::sort(str.begin(), str.end());
   }
   
   for (size_t i = 1; i < strArray.size(); i++) {
      if (strArray[i - 1] != strArray[i]) {
         return false;
      }
   }
   
   return true;
}

int main() {
   std::vector<std::string> strArray = {"abb", "bba", "bab"};
   
   if (canBeMadeSame(strArray)) {
      std::cout << "All strings can be made the same by interchanging characters." << std::endl;
   } else {
      std::cout << "All strings cannot be made the same by interchanging characters." << std::endl;
   }

   return 0;
}

Sortie

All strings can be made the same by interchanging characters.

Complexité temporelle (naïve) : O(n * m * log(m)), où n est le nombre de chaînes dans le tableau et m est la longueur maximale des chaînes dans le tableau.

Méthode efficace

Ce qui fonctionne, c'est de compter la fréquence de chaque caractère dans chaque chaîne et de stocker le nombre dans un tableau de fréquences. Ensuite, comparez les tableaux de fréquences de toutes les chaînes. S'ils sont égaux, cela signifie que toutes les chaînes peuvent être rendues identiques en échangeant les caractères.

Algorithme (efficace)

• Initialisez le vecteur du tableau de fréquences pour chaque chaîne du tableau.

• Comptez la fréquence d'apparition de chaque caractère dans chaque chaîne et stockez-la dans le tableau de fréquences correspondant.

• Comparez les tableaux de fréquences de toutes les chaînes.

• Renvoie vrai si tous les tableaux de fréquences sont égaux ; sinon, renvoie faux.

Code C++ (efficace)

Exemple

#include <iostream>
#include <vector>
#include <algorithm>

bool canBeMadeSame(std::vector<std::string> &strArray) {
   std::vector<std::vector<int>> freqArrays(strArray.size(), std::vector<int>(26, 0));
   
   for (size_t i = 0; i < strArray.size(); i++) {
      for (char ch : strArray[i]) {
         freqArrays[i][ch - 'a']++;
      }
   }
   
   for (size_t i = 1; i < freqArrays.size(); i++) {
      if (freqArrays[i - 1] != freqArrays[i])
      return false;
   }
   
   return true;
}

int main() {
   std::vector<std::string> strArray = {"abb", "bba", "bab"};
   if (canBeMadeSame(strArray)) {
      std::cout << "All strings can be made the same by interchanging characters." << std::endl;
   } else {
      std::cout << "All strings cannot be made the same by interchanging characters." << std::endl;
   }
   
   return 0;
}

Sortie

All strings can be made the same by interchanging characters.

Complexité temporelle (efficace) - O(n * m), où n est le nombre de chaînes dans le tableau et m est la longueur maximale des chaînes dans le tableau.

Conclusion

Dans cet article, nous avons exploré le problème de vérifier si toutes les chaînes d'un tableau sont identiques en échangeant les caractères. Nous discutons de méthodes simples mais efficaces pour résoudre ce problème, ainsi que de leur complexité algorithmique et temporelle. Cette méthode efficace utilise un tableau de fréquences pour comparer le nombre d’occurrences d’un caractère, ce qui entraîne une amélioration significative de la complexité temporelle par rapport à la méthode plus simple.

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!