Rumah  >  Artikel  >  pembangunan bahagian belakang  >  Ubah suai ayat dengan membalikkan susunan semua perkataan palindrom muncul

Ubah suai ayat dengan membalikkan susunan semua perkataan palindrom muncul

WBOY
WBOYke hadapan
2023-08-27 10:01:12687semak imbas

Ubah suai ayat dengan membalikkan susunan semua perkataan palindrom muncul

Pernyataan Masalah

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.

Contoh

Masuk

str = ‘nayan was gone to navjivan eye hospital’

Output

‘eye was gone to navjivan nayan hospital’

Arahan

Rentetan mengandungi tiga palindrom: nayan, navjivan dan mata. Kami membalikkan susunan ketiga-tiga perkataan dan mengekalkan semua perkataan lain sama.

Masuk

‘Hello, users! How are you?’

Output

‘Hello, users! How are you?’

Arahan

Ia memberikan output yang sama kerana rentetan tidak mengandungi sebarang perkataan palindrom.

Masuk

‘Your eye is beautiful.’

Output

‘Your eye is beautiful.’

Arahan

Ia memberikan output yang sama seperti rentetan yang mengandungi hanya satu perkataan palindrom.

Kaedah 1

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.

Algoritma

  • 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.

Contoh

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

Output

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.

Kesimpulan

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!

Kenyataan:
Artikel ini dikembalikan pada:tutorialspoint.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam