Minimieren Sie die Anzahl der erforderlichen Operationen, sodass zwei gegebene Zeichenfolgen Permutationen voneinander sind

In diesem Artikel besprechen wir, wie wir die Anzahl der erforderlichen Operationen minimieren können, um zwei bestimmte Zeichenfolgen aneinander auszurichten. Wir werden dem schrittweisen Ansatz folgen und die Implementierung des C++-Codes bereitstellen. Wir stellen außerdem einen Beispieltestfall zur Verfügung, um das Problem und die Lösung besser zu verstehen.

Problemstellung

Bei zwei Strings s1 und s2 müssen wir die Mindestanzahl an Operationen ermitteln, die erforderlich sind, um s1 und s2 aneinander auszurichten. Wir können zwei Operationen ausführen: zwei beliebige Zeichen von s1 vertauschen oder zwei beliebige Zeichen von s2 vertauschen.

Methodik und Umsetzung

Um dieses Problem zu lösen, müssen wir die Anzahl der Zeichen zählen, die in den beiden Zeichenfolgen nicht vorhanden sind, d. h. den Unterschied in der Häufigkeit des Auftretens von Zeichen in den beiden Zeichenfolgen. Die Mindestanzahl an Vertauschungen, die erforderlich sind, um zwei Zeichenfolgen aneinander auszurichten, entspricht der Hälfte dieser Anzahl, da wir Zeichen in beiden Zeichenfolgen vertauschen können, um sie gleich zu machen.

Zuerst verwenden wir zwei Arrays, um die Häufigkeit von Zeichen in zwei Zeichenfolgen zu berechnen. Anschließend durchlaufen wir die beiden Arrays und addieren die absolute Differenz zwischen den Zeichenhäufigkeiten zu einer Variablen. Diese Variable speichert die Anzahl der Zeichen, die nicht in beiden Zeichenfolgen vorhanden sind.

Nachdem wir die Anzahl berechnet haben, geben wir die Hälfte davon als die Mindestanzahl an Vertauschungen zurück, die erforderlich sind, damit die beiden Zeichenfolgen miteinander vertauscht werden.

Beispiel

Das Folgende ist die C++-Code-Implementierung der oben genannten Methode -

#include<bits/stdc++.h>
using namespace std;

int countMinSwaps(string s1, string s2) {
   int freq1[26] = {0}, freq2[26] = {0}, count = 0;
   for (char c : s1) {
      freq1[c - 'a']++;
   }
   for (char c : s2) {
      freq2[c - 'a']++;
   }
   for (int i = 0; i < 26; i++) {
      count += abs(freq1[i] - freq2[i]);
   }
   return count / 2;
}

int main() {
   string s1 = "hello";
   string s2 = "world";
   int minSwaps = countMinSwaps(s1, s2);
   cout << "Minimum number of swaps required: " << minSwaps << endl;
   return 0;
}

Ausgabe

Minimum number of swaps required: 3

Beispieltestfälle

Betrachten wir die Beispielzeichenfolgen „hello“ und „world“ für diesen Testfall.

Die Frequenzarrays von zwei Strings sind wie folgt -

freq1 = {0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
freq2 = {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}

Wir können sehen, dass das Zeichen „l“ mit der Häufigkeit 2 in s1, aber nur 1 in s2 vorkommt, während das Zeichen „r“ mit der Häufigkeit 1 in s2 vorkommt, aber in s1 fehlt. Daher beträgt die Anzahl der Zeichen, die nicht in beiden Zeichenfolgen vorhanden sind, 3.

Daher beträgt die Mindestanzahl an Vertauschungen, die erforderlich sind, damit zwei Zeichenfolgen miteinander vertauscht werden, 1. Wir können das „l“ in s1 mit dem „r“ in s2 austauschen, um die Zeichenfolgen „herlo“ und „wolld“ zu erhalten, die Permutationen voneinander sind.

Fazit

In diesem Artikel haben wir besprochen, wie man die Anzahl der erforderlichen Operationen minimieren kann, um zwei bestimmte Zeichenfolgen aneinander auszurichten. Wir folgten einem schrittweisen Ansatz und stellten die Implementierung des C++-Codes bereit. Wir stellen auch einen Beispieltestfall zur Verfügung, um das Problem und die Lösung besser zu verstehen. Das Problem kann in O(n)-Zeitkomplexität und O(1)-Raumkomplexität gelöst werden.

Das obige ist der detaillierte Inhalt vonMinimieren Sie die Anzahl der erforderlichen Operationen, sodass zwei gegebene Zeichenfolgen Permutationen voneinander sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!