Vérifie si une permutation d'une chaîne donnée est lexicographiquement supérieure à une autre chaîne donnée

Nous avons reçu deux chaînes et devons vérifier si une permutation de la chaîne donnée existe afin qu'une permutation puisse avoir des caractères plus grands que l'autre permutation au i-ième index.

Nous pouvons résoudre le problème en triant la chaîne et en comparant chaque caractère de la chaîne un par un. Alternativement, nous pouvons utiliser les fréquences de caractères des deux chaînes pour résoudre le problème.

Énoncé du problème - On nous donne des chaînes str1 et str2 de longueur N. Nous devons vérifier s’il existe des permutations de chaînes telles que l’une soit lexicographiquement plus grande que l’autre. Cela signifie que toute permutation doit avoir un caractère au i-ème index qui est supérieur au caractère au i-ème index d'une autre permutation de chaîne.

Exemple

Entrée - str1 = "aef"; str2 = "fgh";

Sortie–Oui

Explication– « fgh » est déjà plus grand que « aef ». Ici, un > ;

Entrée– str1 = "adsm"; str2 = "obpc";

Sortie–Non

Explication– Nous ne trouvons aucune permutation dans laquelle chaque caractère d'une chaîne est plus grand que l'autre.

Méthode 1

Dans cette méthode, nous trierons deux chaînes par ordre lexicographique. Nous comparerons ensuite chaque caractère de la chaîne. Renvoie vrai si tous les caractères de str1 sont inférieurs à str2 ou si tous les caractères de str2 sont inférieurs à str1. Sinon, retournez false.

Algorithme

• Utilisez la méthode sort() pour trier les chaînes.

• Définissez la variable booléenne isStr1Greater et initialisez-la avec true.

• Traversez la chaîne et si le caractère à la i-ème position d'index dans str1 est inférieur à str2, mettez à jour la valeur de isStr1Greater sur false et utilisez le mot-clé break pour interrompre la boucle

• Si isStr1Greater est vrai, la boucle se termine avec succès et renvoie vrai.

• Maintenant, parcourez la chaîne pour vérifier si str2 est supérieur à str1. Si nous constatons qu’un caractère de str1 est supérieur à str2, alors false est renvoyé.

• Renvoie vrai si la boucle se termine avec succès.

Exemple

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

Sortie

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

Complexité temporelle - O(N*logN) car nous trions les chaînes.

Complexité spatiale - O(N) est requis pour trier les chaînes.

Méthode 2

Dans cette méthode, nous stockerons la fréquence totale de chaque caractère dans les deux chaînes. Ensuite, nous utiliserons les fréquences cumulées pour décider si nous pouvons trouver des permutations de chaînes telles que l’une soit supérieure à l’autre.

Algorithme

• Définissez les tableaux map1 et map2 de longueur 26 et initialisez-les à zéro.

• Stockez la fréquence des caractères dans str1 dans map1 et stockez la fréquence des caractères dans str2 dans map2.

• Définissez les variables booléennes isStr1 et isStr2 et initialisez-les à false pour savoir si str1 est supérieur à str2.

• Définissez les variables cnt1 et cnt2 pour stocker la fréquence cumulée des caractères de chaîne.

• Traverse map1 et map2. Ajoutez map1[i] à cnt1 et map2[i] à cnt2.

• Si cnt1 est supérieur à cnt2, la fréquence cumulée des caractères de str1 au i-ième index est plus grande. Si tel est le cas et que str2 est déjà plus grand, renvoyez false. Sinon, remplacez isStr1 par true

• Si cnt2 est supérieur à cnt1, alors la fréquence cumulée du caractère au i-ième index dans str2 est supérieure. Si tel est le cas et que str1 est déjà plus grand, renvoyez false. Sinon, remplacez isStr2 par true

• Renvoie enfin vrai.

Exemple

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

Sortie

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

Complexité temporelle - O(N), puisque nous comptons la fréquence des caractères.

Complexité spatiale - O(26) car nous stockons la fréquence des caractères dans le tableau.

Nous avons appris à vérifier s'il existe une permutation de deux chaînes telle que tous les caractères d'une chaîne peuvent être plus grands que l'autre chaîne. La première méthode utilise une méthode de classement et la seconde méthode utilise la fréquence cumulée des caractères.

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!