Prüfen Sie, ob alle Zeichenfolgen in einem Array durch Vertauschen von Zeichen identisch gemacht werden können

In diesem Artikel untersuchen wir das Problem der Überprüfung, ob alle Zeichenfolgen in einem Array gleich sind, indem wir Zeichen austauschen. Wir werden zunächst die Problemstellung verstehen und dann einfache und effiziente Wege zur Lösung des Problems sowie deren jeweilige Algorithmen und Zeitkomplexität untersuchen. Abschließend werden wir die Lösung in C++ implementieren.

Problemstellung

Bestimmen Sie anhand eines Arrays von Zeichenfolgen, ob alle Zeichenfolgen durch Vertauschen von Zeichen gleich gemacht werden können.

Naive Methode

Die einfachste Möglichkeit besteht darin, die Zeichen jeder Zeichenfolge im Array zu sortieren und dann jede sortierte Zeichenfolge mit der nächsten sortierten Zeichenfolge zu vergleichen. Wenn alle sortierten Zeichenfolgen gleich sind, bedeutet dies, dass alle Zeichenfolgen durch Vertauschen von Zeichen gleich gemacht werden können.

Algorithmus (naiv)

• Sortieren Sie die Zeichen jeder Zeichenfolge im Array.

• Vergleichen Sie jede sortierte Zeichenfolge mit der nächsten sortierten Zeichenfolge.

• Gibt „true“ zurück, wenn alle sortierten Zeichenfolgen gleich sind; andernfalls wird „false“ zurückgegeben.

C++-Code (einfach)

Beispiel

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

Ausgabe

All strings can be made the same by interchanging characters.

Zeitkomplexität (naiv): O(n * m * log(m)), wobei n die Anzahl der Strings im Array und m die maximale Länge der Strings im Array ist.

Effiziente Methode

Was funktioniert, ist, die Häufigkeit jedes Zeichens in jeder Zeichenfolge zu zählen und die Anzahl in einem Häufigkeitsarray zu speichern. Vergleichen Sie dann die Frequenzarrays aller Strings. Wenn sie gleich sind, bedeutet das, dass alle Zeichenfolgen durch Vertauschen von Zeichen gleich gemacht werden können.

Algorithmus (effizient)

• Initialisieren Sie den Frequenz-Array-Vektor für jede Zeichenfolge im Array.

• Zählen Sie die Häufigkeit des Auftretens jedes Zeichens in jeder Zeichenfolge und speichern Sie sie im entsprechenden Häufigkeitsarray.

• Vergleichen Sie Frequenzarrays aller Saiten.

• Gibt „true“ zurück, wenn alle Frequenzarrays gleich sind; andernfalls wird „false“ zurückgegeben.

C++-Code (effizient)

Beispiel

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

Ausgabe

All strings can be made the same by interchanging characters.

Zeitkomplexität (effizient) – O(n * m), wobei n die Anzahl der Strings im Array und m die maximale Länge der Strings im Array ist.

Fazit

In diesem Artikel haben wir uns mit dem Problem befasst, durch Vertauschen von Zeichen zu überprüfen, ob alle Zeichenfolgen in einem Array gleich sind. Wir diskutieren einfache, aber effiziente Methoden zur Lösung dieses Problems sowie deren algorithmische und zeitliche Komplexität. Diese effiziente Methode verwendet ein Frequenzarray, um die Häufigkeit des Vorkommens eines Zeichens zu vergleichen, was zu einer deutlichen Verbesserung der Zeitkomplexität im Vergleich zur einfacheren Methode führt.

Das obige ist der detaillierte Inhalt vonPrüfen Sie, ob alle Zeichenfolgen in einem Array durch Vertauschen von Zeichen identisch gemacht werden können. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!