Rumah > Artikel > pembangunan bahagian belakang > Ubah suai ayat dengan membalikkan susunan semua perkataan palindrom muncul
Kami diberi rentetan str yang mengandungi N perkataan secara keseluruhan. Kita perlu mencari semua perkataan palindrom dalam rentetan tertentu dan mencipta rentetan baharu dengan membalikkan susunan semua perkataan palindrom.
str = ‘nayan was gone to navjivan eye hospital’
‘eye was gone to navjivan nayan hospital’
Rentetan mengandungi tiga palindrom: nayan, navjivan dan mata. Kami membalikkan susunan ketiga-tiga perkataan dan mengekalkan semua perkataan lain sama.
‘Hello, users! How are you?’
‘Hello, users! How are you?’
Ia memberikan output yang sama kerana rentetan tidak mengandungi sebarang perkataan palindrom.
‘Your eye is beautiful.’
‘Your eye is beautiful.’
Ia memberikan output yang sama seperti rentetan yang mengandungi hanya satu perkataan palindrom.
Dalam kaedah ini, kami mula-mula membelah rentetan menjadi perkataan. Selepas itu, kami akan menapis semua perkataan palindrom. Seterusnya, kita membalikkan susunan semua palindrom.
Akhir sekali, kami mengulangi melalui rentetan dan jika perkataan semasa ialah perkataan palindrom, kami menggantikannya dengan perkataan palindrom lain dalam susunan terbalik.
Langkah 1 - Jalankan fungsi reversePlaindromic() dengan menghantar rentetan sebagai argumen yang mengembalikan rentetan hasil.
Langkah 2 - Cipta fungsi isPalindrome() untuk menyemak sama ada sesuatu perkataan ialah palindrom.
Langkah 2.1 - Mulakan "mula" kepada 0 dan "tamat" kepada panjang rentetan - 1.
Langkah 2.2 - Gunakan gelung sementara untuk melelaran melalui rentetan, membandingkan aksara pertama dan terakhir, membandingkan aksara kedua dan kedua terakhir, dan seterusnya. Jika mana-mana aksara tidak sepadan, palsu dikembalikan kerana ia bukan rentetan palindrom.
Langkah 2.3 - Mengembalikan benar jika rentetan ialah palindrom.
Langkah 3 - Buat vektor untuk menyimpan perkataan rentetan. Selain itu, tentukan pembolehubah "temp" untuk menyimpan perkataan.
Langkah 4 - Gunakan gelung for untuk lelaran pada rentetan dan tambahkan aksara pada nilai sementara jika ia tidak sama dengan ruang (‘ ’). Jika tidak, tolak nilai temp ke vektor allWords.
Langkah 5 - Ulangi pada vektor allWords dan semak sama ada perkataan semasa ialah palindrom menggunakan fungsi isPalindrome(). Jika ya, tolak perkataan itu ke dalam vektor "palindromWords".
Langkah 6 - Balikkan senarai "palindromWords".
Langkah 7 - Sekarang, ulangi vektor "allWords" sekali lagi dan semak sama ada perkataan semasa ialah palindrom. Jika ya, gantikannya dengan perkataan yang dihormati daripada senarai "palindromWords".
Langkah 8 - Ulangi senarai "palindromWords" dan buat rentetan dengan menambahkan semua perkataan pada pembolehubah hasil. Mengembalikan rentetan hasil.
#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
Kerumitan masa - O(N) kerana kita mengulangi rentetan panjang N.
Kerumitan Ruang - O(K) kerana kami menggunakan senarai untuk menyimpan perkataan, di mana k ialah jumlah bilangan perkataan dalam rentetan.
Kami belajar mengambil semua perkataan palindrom daripada ayat dan menambahnya dalam susunan terbalik. Dalam kod di atas, pengaturcara boleh cuba menukar pelaksanaan fungsi isPalindrome() untuk mempelajari sesuatu yang baharu.
Atas ialah kandungan terperinci Ubah suai ayat dengan membalikkan susunan semua perkataan palindrom muncul. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!