Überprüft, ob eine Permutation einer bestimmten Zeichenfolge lexikographisch größer ist als eine andere angegebene Zeichenfolge

Wir haben zwei Zeichenfolgen erhalten und müssen prüfen, ob eine Permutation der angegebenen Zeichenfolge existiert, damit eine Permutation am i-ten Index größere Zeichen als die andere Permutation haben kann.

Wir können das Problem lösen, indem wir die Zeichenfolge sortieren und jedes Zeichen in der Zeichenfolge einzeln vergleichen. Alternativ können wir die Zeichenhäufigkeiten der beiden Zeichenfolgen verwenden, um das Problem zu lösen.

Problemstellung – Wir erhalten die Zeichenfolgen str1 und str2 der Länge N. Wir müssen prüfen, ob es Permutationen von Zeichenfolgen gibt, sodass eine lexikographisch größer ist als die andere. Dies bedeutet, dass jede Permutation ein Zeichen am i-ten Index haben sollte, das größer ist als das Zeichen am i-ten Index einer anderen Zeichenfolgenpermutation.

Beispiel

Eingabe - str1 = "aef"; str2 = "fgh";

Ausgabe – Ja

Erklärung – „fgh“ ist bereits größer als „aef“. Hier gilt a > f, g >

Eingabe– str1 = „adsm“; str2 = „obpc“;

Ausgabe – Nein

Erklärung– Wir können keine Permutation finden, bei der jedes Zeichen einer Zeichenfolge größer als das andere ist.

Methode 1

Bei dieser Methode sortieren wir zwei Zeichenfolgen in lexikografischer Reihenfolge. Anschließend vergleichen wir jedes Zeichen der Zeichenfolge. Gibt „true“ zurück, wenn alle Zeichen von str1 kleiner als str2 sind oder wenn alle Zeichen von str2 kleiner als str1 sind. Andernfalls wird false zurückgegeben.

Algorithmus

• Verwenden Sie die Methode sort(), um Zeichenfolgen zu sortieren.

• Definieren Sie die boolesche Variable isStr1Greater und initialisieren Sie sie mit true.

• Durchlaufen Sie die Zeichenfolge. Wenn das Zeichen an der i-ten Indexposition in str1 kleiner als str2 ist, aktualisieren Sie den Wert von isStr1Greater auf false und unterbrechen Sie die Schleife mit dem Schlüsselwort break.

• Wenn isStr1Greater true ist, wird die Schleife erfolgreich abgeschlossen und gibt true zurück.

• Durchlaufen Sie nun die Zeichenfolge, um zu prüfen, ob str2 größer als str1 ist. Wenn wir feststellen, dass ein Zeichen von str1 größer als str2 ist, wird false zurückgegeben.

• Gibt true zurück, wenn die Schleife erfolgreich abgeschlossen wird.

Beispiel

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

bool isAnyPermLarge(string string1, string string2) {
   // sort the strings
   sort(string1.begin(), string1.end());
   sort(string2.begin(), string2.end());
   // to keep track if string1 is greater than string2
   bool isStr1Greater = true;
   // traverse the string
   for (int i = 0; i < string1.length(); i++) {
      // if any character of string1 is less than string2, return false.
      if (string1[i] < string2[i]) {
          isStr1Greater = false;
          break;
      }
   }
   // If string1 is greater, returning true
   if (isStr1Greater)
      return true;
   // traverse the string
   for (int i = 0; i < string2.length(); i++) {
      // if any character of string2 is less than string1, return false.
      if (string1[i] > string2[i]) {
          return false;
      }
   }
   // return true if string2 is greater than string1
   return true;
}
int main() {
   string string1 = "aef";
   string string2 = "fgh";
   bool res = isAnyPermLarge(string1, string2);
   if (res) {
      cout << "Yes, permutation exists such that one string is greater than the other.";
   } else {
      cout << "No, permutation does not exist such that one string is greater than the other.";
   }
   return 0;
}

Ausgabe

Yes, permutation exists such that one string is greater than the other.

Zeitkomplexität – O(N*logN), weil wir die Strings sortieren.

Raumkomplexität – O(N) ist zum Sortieren von Zeichenfolgen erforderlich.

Methode 2

Bei dieser Methode speichern wir die Gesamthäufigkeit jedes Zeichens in beiden Zeichenfolgen. Anschließend werden wir die kumulativen Häufigkeiten verwenden, um zu entscheiden, ob wir Permutationen von Zeichenfolgen finden können, bei denen eine größer als die andere ist.

Algorithmus

• Definieren Sie die Arrays „map1“ und „map2“ mit der Länge 26 und initialisieren Sie sie auf Null.

• Speichern Sie die Häufigkeit der Zeichen in str1 in Map1 und speichern Sie die Häufigkeit der Zeichen in str2 in Map2.

• Definieren Sie die booleschen Variablen isStr1 und isStr2 und initialisieren Sie sie mit „false“, um zu verfolgen, ob str1 größer als str2 ist.

• Definieren Sie die Variablen cnt1 und cnt2, um die kumulative Häufigkeit von Zeichenfolgenzeichen zu speichern.

• Durchqueren Sie Karte1 und Karte2. Fügen Sie „map1[i]“ zu „cnt1“ und „map2[i]“ zu „cnt2“ hinzu.

• Wenn cnt1 größer als cnt2 ist, ist die kumulative Häufigkeit der Zeichen von str1 bis zum i-ten Index größer. Wenn ja und str2 bereits größer ist, wird „false“ zurückgegeben. Andernfalls ändern Sie isStr1 in true

• Wenn cnt2 größer als cnt1 ist, ist die kumulative Häufigkeit des Zeichens am i-ten Index in str2 größer. Wenn ja und str1 bereits größer ist, wird „false“ zurückgegeben. Andernfalls ändern Sie isStr2 in true

• Endlich gibt true zurück.

Beispiel

#include <iostream>
#include <string>
using namespace std;

bool isAnyPermLarge(string string1, string string2) {
   int map1[26] = {0};
   int map2[26] = {0};
   // store the frequency of each character in the map1
   for (int i = 0; i < string1.length(); i++) {
      map1[string1[i] - 'a']++;
   }
   // store the frequency of each character in the map2
   for (int i = 0; i < string2.length(); i++) {
      map2[string2[i] - 'a']++;
   }
   // To keep track of which string is smaller. Initially, both strings are equal.
   bool isStr1 = false, isStr2 = false;
   // to count the cumulative frequency of characters of both strings
   int cnt1 = 0, cnt2 = 0;
   // traverse for all characters.
   for (int i = 0; i < 26; i++) {
      // update the cumulative frequency of characters
      cnt1 += map1[i];
      cnt2 += map2[i];
      if (cnt1 > cnt2) {
          // If string2 is already greater and cumulative frequency of string1 is greater than string2, then return false
          if (isStr2)
              return false;
          // update isStr1 to true as string1 is smaller
          isStr1 = true;
      }
      if (cnt1 < cnt2) {
          // If string1 is already greater and cumulative frequency of string2 is greater than string1, then return false
          if (isStr1)
              return false;
          // update isStr2 to true as string2 is smaller
          isStr2 = true;
      }
   }
   return true;
}
int main() {
   string string1 = "aef";
   string string2 = "fgh";
   bool res = isAnyPermLarge(string1, string2);
   if (res) {
      cout << "Yes, permutation exists such that one string is greater than the other.";
   } else {
      cout << "No, permutation does not exist such that one string is greater than the other.";
   }
   return 0;
}

Ausgabe

Yes, permutation exists such that one string is greater than the other.

Zeitkomplexität – O(N), da wir die Häufigkeit von Zeichen zählen.

Raumkomplexität – O(26), weil wir die Häufigkeit der Zeichen im Array speichern.

Wir haben gelernt, zu prüfen, ob es eine Permutation zweier Zeichenfolgen gibt, sodass alle Zeichen einer Zeichenfolge größer sein können als die der anderen Zeichenfolge. Die erste Methode verwendet eine Sortiermethode und die zweite Methode verwendet die kumulative Häufigkeit von Zeichen.

Das obige ist der detaillierte Inhalt vonÜberprüft, ob eine Permutation einer bestimmten Zeichenfolge lexikographisch größer ist als eine andere angegebene Zeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!