Inverser les mots en utilisant un espace supplémentaire O(1)

Une chaîne peut être composée de plusieurs mots. Chaque mot d'une chaîne C++ peut contenir des lettres, des chiffres ou des symboles spéciaux. Les chaînes sont considérées comme des éléments de stockage de ces caractères. Chaque mot est séparé par un espace. Chaque mot forme également une chaîne d'un caractère. En C++, l'inverse de n'importe quelle chaîne est une chaîne qui suit −

• Il est formé en prenant des personnages de la fin vers le début.

• La longueur de la chaîne d'origine reste inchangée.

L'ordre dans lequel les caractères apparaissent dans une chaîne peut être facilement inversé en échangeant les caractères au début et à la fin du mot.

L'espace auxiliaire constant est représenté par O(1), ce qui signifie que le programme ne nécessite pas d'espace supplémentaire lors de l'exécution.

Quelques exemples pour illustrer le problème sont les suivants :

Exemple Exemple

Exemple 1 - str:Abc def

Sortie : cbA fed

Explication : Lors de l'inversion d'une chaîne, la condition des caractères reste inchangée.

Exemple 2 - str : Salut spe%32

Sortie : ouais 23 % eps

L'énoncé du problème peut être résolu en extrayant chaque mot et en conservant une paire de pointeurs de début et de fin pour chaque mot, puis en l'inversant.

Algorithme

• Étape 1−Utilisez une boucle for pour parcourir la chaîne d'entrée fournie.

• Étape 2 - Capturez le caractère de départ du premier mot en utilisant la variable st.

• Étape 3 - Une fois le premier espace rencontré, la variable lst est fixée sur le caractère précédent pour marquer les caractères de début et de fin du mot.

• Étape 4 - À l'aide de ces deux pointeurs et d'une boucle while, inversez les caractères du mot. A chaque itération de la boucle while, le pointeur est déplacé pour épuiser la chaîne.

• Étape 5 - Les valeurs sont mises à jour pour déplacer les pointeurs vers le mot suivant suivant et ainsi de suite est réinitialisé au caractère suivant après l'espace.

.

• Étape 6 - La chaîne entière est itérée et les mots correspondants sont inversés.

Exemple

L'extrait de code C++ suivant prend une chaîne en entrée et inverse les mots qu'elle contient -

// including the required libraries
#include <bits/stdc++.h>
using namespace std;

//reversing current word of string
void reverseWord(string &st, int s, int e){
   while (s < e) {
      swap(st[s], st[e]);
      s++;
      e--;
   }
}

//reverse the words of a string
string reverseString(string str){
   int len = str.length();

   //initialising the pointer with the first letter of the input string
   int st = 0;
   for (int i = 0; i <= len; i++) {

      //stop the pointer at the first word
      //either a space will be found indicating end of word or the string is finished
      char ch = str[i];
      if (ch == ' ' || i == len) {

         //fetching the last character of the current word of the string
         int lst = i - 1;

         // Reverse the current word
         reverseWord(str, st,lst);

         //since the ith character is string , go to i+1 th character to fetch next word
         st = i + 1;
      }
   }
   return str;
}

//calling the method to reverse words
int main(){

   //input string
   string str = "Reverse words Tutorials Point";
   cout<<"original String:"<<str;

   //reversed string
   string revstr = reverseString(str);
   cout << "\nReversed string : "<< revstr;
   return 0;
}

Sortie

original String:Reverse words Tutorials Point
Reversed string : esreveR sdrow slairotuT tnioP

Complexité spatiale

L'espace requis par la méthode ci-dessus est constant puisqu'il n'y a pas de nouvelle initialisation d'aucun type de variable. Aucun espace de stockage externe n'est requis pour échanger des mots. Toutes les modifications sont apportées aux variables de stockage disponibles.

Conclusion

Les chaînes sont composées de caractères qui peuvent être disposés dans n'importe quel ordre ou inversés par simple itération. Étant donné que l'algorithme effectue une seule itération pour toute la plage de caractères qui y est stockée, le temps total requis est O(n), où n est la longueur de la chaîne.

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!