Kehren Sie Wörter mit O(1) zusätzlichem Leerzeichen um

Eine Zeichenfolge kann aus mehreren Wörtern bestehen. Jedes Wort in einer C++-Zeichenfolge kann Buchstaben, Zahlen oder Sonderzeichen enthalten. Als Speicherelemente für diese Zeichen gelten Strings. Jedes Wort wird durch ein Leerzeichen getrennt. Jedes Wort bildet auch eine Zeichenfolge aus einem Zeichen. In C++ ist die Umkehrung einer beliebigen Zeichenfolge eine Zeichenfolge, die auf −

folgt

• Es entsteht, indem die Charaktere vom Ende zum Anfang geführt werden.

• Die Länge der Originalzeichenfolge bleibt unverändert.

Die Reihenfolge, in der Zeichen in einer Zeichenfolge erscheinen, kann leicht umgekehrt werden, indem die Zeichen am Anfang und Ende des Wortes vertauscht werden.

Konstanter Hilfsraum wird durch O(1) dargestellt, was bedeutet, dass das Programm während der Ausführung keinen zusätzlichen Speicherplatz benötigt.

Einige Beispiele zur Veranschaulichung des Problems sind wie folgt:

Beispiel Beispiel

Beispiel 1 – str:Abc def

Ausgabe: cbA gefüttert

Erklärung: Beim Umkehren einer Zeichenfolge bleibt der Zustand der Zeichen unverändert.

Beispiel 2 – str: Hi spe%32

Ausgabe: Ja, 23 % EPS

Die Problemstellung kann gelöst werden, indem jedes Wort extrahiert und ein Paar Start- und Endzeiger für jedes Wort beibehalten und dann invertiert wird.

Algorithmus

• Schritt 1−Verwenden Sie eine for-Schleife, um die bereitgestellte Eingabezeichenfolge zu durchlaufen.

• Schritt 2 – Verwenden Sie die Variable st, um das Anfangszeichen des ersten Wortes zu erfassen.

• Schritt 3 − Sobald das erste Leerzeichen gefunden wird, wird die Variable lst auf das vorherige Zeichen fixiert, um die Anfangs- und Endzeichen des Wortes zu markieren.

• Schritt 4 − Mit diesen beiden Zeigern und einer While-Schleife kehren Sie die Zeichen des Wortes um. Bei jeder Iteration der while-Schleife wird der Zeiger bewegt, um die Zeichenfolge zu erschöpfen.

• Schritt 5 - Die Werte werden aktualisiert, um die Zeiger auf das nächste nachfolgende Wort zu verschieben, und so wird st auf das nächste Zeichen nach dem Leerzeichen neu initialisiert.

• Schritt 6 – Die gesamte Zeichenfolge wird iteriert und die entsprechenden Wörter werden umgekehrt.

Beispiel

Der folgende C++-Codeausschnitt nimmt eine Zeichenfolge als Eingabe und kehrt die darin enthaltenen Wörter um -

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

Ausgabe

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

Weltraumkomplexität

Der von der oben genannten Methode benötigte Speicherplatz ist konstant, da keine neue Initialisierung von Variablen jeglicher Art erfolgt. Zum Austauschen von Wörtern ist kein externer Speicherplatz erforderlich. Alle Änderungen werden in verfügbaren Speichervariablen vorgenommen.

Fazit

Strings bestehen aus Zeichen, die in beliebiger Reihenfolge angeordnet oder durch einfache Iteration umgekehrt werden können. Da der Algorithmus eine einzelne Iteration für den gesamten darin gespeicherten Zeichenbereich durchführt, beträgt die erforderliche Gesamtzeit O(n), wobei n die Länge der Zeichenfolge ist.

Das obige ist der detaillierte Inhalt vonKehren Sie Wörter mit O(1) zusätzlichem Leerzeichen um. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!