Ändern Sie den Satz, indem Sie die Reihenfolge umkehren, in der alle palindromischen Wörter erscheinen

Problemstellung

Wir erhalten eine Zeichenfolge str, die insgesamt N Wörter enthält. Wir müssen alle Palindrom-Wörter in einer bestimmten Zeichenfolge finden und eine neue Zeichenfolge erstellen, indem wir die Reihenfolge aller Palindrom-Wörter umkehren.

Beispiel

Eintreten

str = ‘nayan was gone to navjivan eye hospital’

Ausgabe

‘eye was gone to navjivan nayan hospital’

Anleitung

Die Zeichenfolge enthält drei Palindrome: Nayan, Navjivan und Eye. Wir haben die Reihenfolge aller drei Wörter umgekehrt und alle anderen Wörter beibehalten.

Eintreten

‘Hello, users! How are you?’

Ausgabe

‘Hello, users! How are you?’

Anleitung

Es ergibt die gleiche Ausgabe, da die Zeichenfolge keine Palindrom-Wörter enthält.

Eintreten

‘Your eye is beautiful.’

Ausgabe

‘Your eye is beautiful.’

Anleitung

Es liefert die gleiche Ausgabe wie eine Zeichenfolge, die nur ein einziges Palindromwort enthält.

Methode 1

Bei dieser Methode teilen wir die Zeichenfolge zunächst in Wörter auf. Danach filtern wir alle Palindromwörter. Als nächstes kehren wir die Reihenfolge aller Palindrome um.

Abschließend durchlaufen wir die Zeichenfolge und wenn das aktuelle Wort ein Palindrom-Wort ist, ersetzen wir es in umgekehrter Reihenfolge durch ein anderes Palindrom-Wort.

Algorithmus

• Schritt 1 – Führen Sie die Funktion reversePlaindromic() aus, indem Sie einen String als Argument übergeben, der den Ergebnisstring zurückgibt.

• Schritt 2 – Erstellen Sie die Funktion isPalindrome(), um zu überprüfen, ob ein Wort ein Palindrom ist.

• Schritt 2.1 – Initialisieren Sie „Start“ auf 0 und „Ende“ auf die Zeichenfolgenlänge – 1.

• Schritt 2.2 – Verwenden Sie eine While-Schleife, um die Zeichenfolge zu durchlaufen, das erste und letzte Zeichen zu vergleichen, das zweite und vorletzte Zeichen zu vergleichen und so weiter. Wenn irgendwelche Zeichen nicht übereinstimmen, wird „false“ zurückgegeben, da es sich nicht um eine Palindromzeichenfolge handelt.

• Schritt 2.3 – Gibt true zurück, wenn die Zeichenfolge ein Palindrom ist.

• Schritt 3 – Erstellen Sie einen Vektor, um die Wörter der Zeichenfolge zu speichern. Definieren Sie außerdem die Variable „temp“, um das Wort zu speichern.

• Schritt 4 – Durchlaufen Sie die Zeichenfolge mit einer for-Schleife und hängen Sie das Zeichen an den temporären Wert an, wenn es nicht einem Leerzeichen (‘ ’) entspricht. Andernfalls verschieben Sie den Wert von temp in den allWords-Vektor.

• Schritt 5 – Iterieren Sie über den allWords-Vektor und prüfen Sie mithilfe der Funktion isPalindrome(), ob das aktuelle Wort ein Palindrom ist. Wenn ja, schieben Sie das Wort in den Vektor „palindromWords“.

• Schritt 6 – Kehren Sie die Liste „palindromWords“ um.

• Schritt 7 – Nun iterieren Sie erneut über den „allWords“-Vektor und prüfen Sie, ob das aktuelle Wort ein Palindrom ist. Wenn ja, ersetzen Sie es durch ein angesehenes Wort aus der Liste „palindromWords“.

• Schritt 8 – Durchlaufen Sie die Liste „palindromWords“ und erstellen Sie eine Zeichenfolge, indem Sie alle Wörter an die Ergebnisvariable anhängen. Gibt die Ergebniszeichenfolge zurück.

Beispiel

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to check if a string is a palindrome
bool isPalindrome(string str){
   int start = 0;
   int end = str.length() - 1;
   // iterate till start < end
   while (start < end){
      // check if the character at the start and end are not the same and return false, else increment start and decrement end
      if (str[start] != str[end]){
         return false;
      } else {
         start++;
         end--;
      }
   }
   return true;
}
string reversePalindromic(string str) {
   // vectors to store all words and palindromic words
   vector<string> palindromWords;
   vector<string> allWords;
   // variable to store single word
   string temp = "";
   for (char x : str) {
      // If the current character is not space, then append it to temp; else, add temp to palindrome words and make temp NULL
      if (x != ' ') {
         temp += x;
      } else {
         allWords.push_back(temp);
         temp = "";
      }
   }
   // push the last word to all words
   allWords.push_back(temp);
   // fetch all palindromic words
   for (string x : allWords){
      if (isPalindrome(x)){
         // Update newlist
         palindromWords.push_back(x);
      }
   }
   // Reverse the vector
   reverse(palindromWords.begin(), palindromWords.end());
   int k = 0;
   for (int i = 0; i < allWords.size(); i++){
      // If the current word is a palindrome, push it to palindrome words
      if (isPalindrome(allWords[i])){
         allWords[i] = palindromWords[k];
         k++;
      }
   }
   string result = "";
   for (string x : allWords) {
      result += x;
      result += " ";
   }
   return result;
}
int main(){
   string str = "nayan was gone to navjivan eye hospital";
   string reverse = reversePalindromic(str);
   cout << reverse << endl;
   return 0;
}

Ausgabe

eye was gone to navjivan nayan hospital

• Zeitkomplexität - O(N), da wir über Strings der Länge N iterieren.

• Raumkomplexität – O(K), weil wir eine Liste zum Speichern von Wörtern verwenden, wobei k die Gesamtzahl der Wörter in der Zeichenfolge ist.

Fazit

Wir haben gelernt, alle Palindrom-Wörter aus einem Satz zu nehmen und sie in umgekehrter Reihenfolge hinzuzufügen. Im obigen Code kann der Programmierer versuchen, die Implementierung der Funktion isPalindrome() zu ändern, um etwas Neues zu lernen.

Das obige ist der detaillierte Inhalt vonÄndern Sie den Satz, indem Sie die Reihenfolge umkehren, in der alle palindromischen Wörter erscheinen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!