Modifiez la phrase en inversant l'ordre dans lequel tous les mots palindromes apparaissent

Énoncé du problème

Nous recevons une chaîne str contenant N mots au total. Nous devons trouver tous les mots palindromes dans une chaîne donnée et créer une nouvelle chaîne en inversant l’ordre de tous les mots palindromes.

Exemple

Entrez

str = ‘nayan was gone to navjivan eye hospital’

Sortie

‘eye was gone to navjivan nayan hospital’

Instructions

La chaîne contient trois palindromes : nayan, navjivan et eye. Nous avons inversé l’ordre des trois mots et gardé tous les autres mots identiques.

Entrez

‘Hello, users! How are you?’

Sortie

‘Hello, users! How are you?’

Instructions

Cela donne le même résultat car la chaîne ne contient aucun mot palindrome.

Entrez

‘Your eye is beautiful.’

Sortie

‘Your eye is beautiful.’

Instructions

Il donne le même résultat qu’une chaîne contenant un seul mot palindrome.

Méthode 1

Dans cette méthode, nous divisons d'abord la chaîne en mots. Après cela, nous filtrerons tous les mots palindromes. Ensuite, nous inversons l’ordre de tous les palindromes.

Enfin, nous parcourons la chaîne et si le mot actuel est un mot palindrome, nous le remplaçons par un autre mot palindrome dans l'ordre inverse.

Algorithme

• Étape 1 - Exécutez la fonction reversePlaindromic() en passant une chaîne comme argument qui renvoie la chaîne résultat.

• Étape 2 - Créez la fonction isPalindrome() pour vérifier si un mot est un palindrome.

• Étape 2.1 - Initialisez « start » à 0 et « end » à la longueur de la chaîne – 1.

• Étape 2.2 - Utilisez une boucle while pour parcourir la chaîne, en comparant le premier et le dernier caractères, en comparant le deuxième et l'avant-dernier caractères, et ainsi de suite. Si des caractères ne correspondent pas, false est renvoyé car il ne s'agit pas d'une chaîne palindrome.

• Étape 2.3 - Renvoie vrai si la chaîne est un palindrome.

• Étape 3 - Créez un vecteur pour stocker les mots de la chaîne. De plus, définissez la variable "temp" pour stocker le mot.

• Étape 4 - Parcourez la chaîne à l'aide d'une boucle for et ajoutez le caractère à la valeur temporaire s'il n'est pas égal à un espace (« »). Sinon, transférez la valeur de temp vers le vecteur allWords.

• Étape 5 - Parcourez le vecteur allWords et vérifiez si le mot actuel est un palindrome à l'aide de la fonction isPalindrome(). Si c'est le cas, poussez le mot dans le vecteur "palindromWords".

• Étape 6 - Inversez la liste "palindromWords".

• Étape 7 - Maintenant, parcourez à nouveau le vecteur "allWords" et vérifiez si le mot actuel est un palindrome. Si tel est le cas, remplacez-le par un mot respecté de la liste "palindromWords".

• Étape 8 - Parcourez la liste "palindromWords" et créez une chaîne en ajoutant tous les mots à la variable de résultat. Renvoie la chaîne de résultat.

Exemple

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

Sortie

eye was gone to navjivan nayan hospital

• Complexité temporelle - O(N) puisque nous parcourons des chaînes de longueur N.

• Complexité spatiale - O(K) car nous utilisons une liste pour stocker des mots, où k est le nombre total de mots dans la chaîne.

Conclusion

Nous avons appris à prendre tous les mots palindromes d'une phrase et à les ajouter dans l'ordre inverse. Dans le code ci-dessus, le programmeur peut essayer de modifier l’implémentation de la fonction isPalindrome() pour apprendre quelque chose de nouveau.

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!