Vérifie si une chaîne peut être réduite lexicographiquement en inversant n'importe quelle sous-chaîne

En C++, nous avons une fonction reverse() intégrée pour inverser une sous-chaîne afin de vérifier si une chaîne peut devenir plus petite lexicographiquement. L'ordre du dictionnaire est le processus de tri des caractères d'un mot dans l'ordre du dictionnaire.

Prenons un exemple de chaîne pour vérifier si l'ordre lexicographique est plus petit.

• Nous comparerons les deux mots pour vérifier le mot lexicographiquement plus petit et prendrons deux chaînes, à savoir 'apple' et 'army'. La première lettre des deux chaînes commence par la lettre ‘a’. Lorsque nous examinons le deuxième caractère des deux lettres, par ordre alphabétique, ‘p’ vient avant ‘r’. Par conséquent, lexicographiquement, pomme est plus petite que armée.

• Dans la chaîne "tutorialspoint", inverser la sous-chaîne "oria" donne "airo", qui est lexicographiquement plus petit. Ensuite, écrivez la chaîne finale sous la forme "tutairolspoint".

• Dans la chaîne "tutorix", inversez la sous-chaîne "tori" pour obtenir "irot", car le caractère de départ de la première sous-chaîne est 't', et la seconde La sous-chaîne est ' i', donc 'i' vient avant 't' dans l'alphabet, donc 'irot' est lexicographiquement plus petit que 'tori'. Écriture finale des cordes "tuirotx"

Prenons un autre exemple de chaîne, tel que "acwz".

Grammaire

reverse( str_name.begin(), str_name.end() )

Instructions

La fonction reverse fait partie de la bibliothèque standard C++. Elle accepte deux paramètres "str_name.begin()" et "str_name.end()".

• str_name est un nom de chaîne suggéré par l'utilisateur.

• begin() et end() sont des fonctions intégrées prédéfinies utilisées sous la fonction inverse. Le travail de la fonction start est de renvoyer un itérateur pointant vers le premier caractère de la chaîne d’entrée. La fonction end renvoie un itérateur qui pointe vers une position avant le dernier caractère de la chaîne d'entrée.

Veuillez noter que la fonction reverse ne renvoie rien car elle modifie directement le conteneur (str_name).

Algorithme

• Tout d'abord, nous utiliserons les trois fichiers d'en-tête nécessaires, à savoir iostream, string et include

• Nous allons commencer par la fonction principale où nous déclarons une variable de chaîne appelée ‘str’ et y stockons la chaîne ‘tutorialspoint’. Nous déclarerons ensuite la variable booléenne ‘isReverse’ comme ‘false’ pour indiquer que la chaîne donnée n’a pas été inversée et est toujours dans sa forme originale.

• Nous créerons ensuite deux boucles for imbriquées pour vérifier chaque sous-chaîne possible de ‘str’. La sous-chaîne est ensuite stockée dans une chaîne temporaire nommée ‘temp’.

• Après cela, nous appelons la fonction 'reverse()' pour inverser la sous-chaîne 'j' stockée dans la variable 'temp' entre les indices 'i' et .

• Créez plus tard une instruction if pour vérifier si la chaîne inversée est lexicographiquement inférieure aux variables 'temp' et 'str' à des fins de comparaison.

• Le compilateur comparera les variables temp et str. S'ils sont tous les deux égaux, alors la variable 'isReverse' sera définie sur true et brisera l'instruction if.

• Maintenant, nous vérifions la valeur de isReverse et si elle est vraie, imprimons l'instruction conditionnelle if, sinon imprimons l'instruction conditionnelle else.

• Quittez le programme.

Exemple

Dans ce programme, nous apprendrons comment réduire lexicographiquement une chaîne en inversant n'importe quelle sous-chaîne.

#include <iostream>
#include <string>
#include <algorithm> 
using namespace std;
int main() {
   string str = "tutorialspoint";
   // User can change this to test other strings such as acwz, groffer, etc
   bool isReverse = false; // it is used to indicate whether or not a substring has been found in the original string “str”.


   // use the loop through all possible substrings of str
   for (int i = 0; i < str.length(); i++) {
      for (int j = i+1; j < str.length(); j++) {
         string temp = str; 
         // create new temporary variable to store the value of str.
         // reverse the substring of i and j
         reverse ( temp.begin() + i, temp.begin() + j + 1 ); 
         // reverse function follow the header file name as <algorithm>
         if (temp < str) { 
            // Check whether the reversed string is lexicographically smaller
            isReverse = true;
            break;
         }
      }
   }
   if ( isReverse ) {
      cout << "Yes, this is lexicographically smaller by reversing a  substring." << endl;
   } else {
      cout << "No, this is not lexicographically smaller by reversing a substring." << endl;
   }
   return 0;
}

Sortie

Si nous entrons la valeur "tutorialspoint", nous obtiendrons le résultat suivant -

Yes, this is lexicographically smaller by reversing a  substring.

Si on rentre la valeur "acwz" on obtient le résultat suivant :

No, this is not lexicographically smaller by reversing a substring.

Conclusion

Nous avons vu comment utiliser des variables de chaîne pour calculer la plus petite valeur dans un dictionnaire en inversant n'importe quelle sous-chaîne. Ensuite, nous définissons la variable chaîne sur une variable temporaire. Nous utilisons ensuite la fonction prédéfinie "reverse()" pour calculer les mots du dictionnaire sous leur forme inverse. Ensuite, nous vérifions la plus petite lexicographiquement en comparant les variables temp et str et obtenons le résultat.

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!