问题陈述

我们给出了一个字符串 str，总共包含 N 个单词。我们需要找到给定字符串中的所有回文单词，并通过反转所有回文单词的顺序来创建一个新字符串。

示例

输入

str = ‘nayan was gone to navjivan eye hospital’

输出

‘eye was gone to navjivan nayan hospital’

说明

该字符串包含三个回文词：nayan、navjivan 和 eye。我们颠倒了所有三个单词的顺序，并保持所有其他单词相同。

输入

‘Hello, users! How are you?’

输出

‘Hello, users! How are you?’

说明

它提供相同的输出，因为字符串不包含任何回文单词。

输入

‘Your eye is beautiful.’

输出

‘Your eye is beautiful.’

说明

它提供与仅包含单个回文单词的字符串相同的输出。

方法 1

在这种方法中，我们首先将字符串拆分为单词。之后，我们将过滤所有回文词。接下来，我们反转所有回文词的顺序。

最后，我们遍历字符串，如果当前单词是回文单词，我们将用另一个回文单词以相反的顺序替换它。

算法

• 步骤 1 - 通过传递一个字符串作为返回结果字符串的参数来执行reversePlaindromic()函数。

• 第 2 步 - 创建 isPalindrome() 函数，用于检查单词是否为回文。

• 步骤 2.1 - 将“start”初始化为 0，将“end”初始化为字符串长度 – 1。

• 步骤 2.2 - 使用 while 循环遍历字符串，比较第一个和最后一个字符，比较第二个和倒数第二个字符，依此类推。如果任何字符不匹配，则返回 false，因为它不是回文字符串。

• 步骤 2.3 - 如果字符串是回文，则返回 true。

• 第 3 步 - 创建一个向量来存储字符串的单词。另外，定义“temp”变量来存储该单词。

• 步骤 4 - 使用 for 循环遍历字符串，如果不等于空格 (‘ ’)，则将字符附加到临时值。否则，将 temp 的值推送到 allWords 向量。

• 步骤 5 - 迭代 allWords 向量并使用 isPalindrome() 函数检查当前单词是否为回文。如果是，则将该单词推入“palindromWords”向量。

• 第 6 步 - 反转“palindromWords”列表。

• 第 7 步 - 现在，再次迭代“allWords”向量，并检查当前单词是否是回文。如果是，请将其替换为“palindromWords”列表中受尊重的单词。

• 第 8 步 - 迭代“palindromWords”列表，并通过将所有单词附加到结果变量来创建一个字符串。返回结果字符串。

示例

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

输出

eye was gone to navjivan nayan hospital

• 时间复杂度 - O(N)，因为我们迭代长度为 N 的字符串。

• 空间复杂度 - O(K)，因为我们使用列表来存储单词，其中 k 是字符串中的单词总数。

结论

我们学会了从句子中获取所有回文单词并以相反的顺序添加它们。在上面的代码中，程序员可以尝试更改 isPalindrome() 函数的实现来学习新的东西。