问题陈述
我们给出了一个字符串 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() 函数的实现来学习新的东西。
