資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究透過反轉所有迴文單詞的出現順序來修改句子
問題陳述
給定一個包含 N 個單詞的字串 str。我們需要找到給定字串中的所有迴文單詞，並透過反轉所有迴文單詞的順序來建立一個新字串。
示例
輸入
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。否則，將 temp 的值推送到 allWords 向量。
步驟 5 - 遍歷 allWords 向量並使用 isPalindrome() 函式檢查當前單詞是否為迴文。如果是，則將單詞推送到 'palindromWords' 向量。
步驟 6 - 反轉 'palindromWords' 列表。
步驟 7 - 現在，再次遍歷 'allWords' 向量，並檢查當前單詞是否為迴文。如果是，則將其替換為 'palindromWords' 列表中相應的單詞。
步驟 8 - 遍歷 'palindromWords' 列表，並透過將所有單詞附加到 result 變數來建立一個字串。返回結果字串。
示例
#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() 函式的實現以學習新知識。
117 次檢視
