Subrentetan terkecil yang perlu dikeluarkan untuk menjadikan rentetan yang diberikan sebagai palindrom

Palindrom ialah jujukan aksara yang berbunyi sama dalam kedua-dua arah ke hadapan dan ke belakang. Dalam sains komputer dan pengaturcaraan, palindrom adalah tema biasa dalam masalah manipulasi rentetan. Dalam artikel ini, kita akan meneroka cara mencari subrentetan saiz minimum yang mesti dialih keluar daripada rentetan tertentu untuk menjadikannya palindrom. Kami akan menyediakan penyelesaian C++ yang tersusun dengan baik dan menyertakan contoh untuk menggambarkan kes ujian.

Pernyataan Masalah

Memandangkan rentetan 's' panjang 'n', kita perlu mencari saiz minimum subrentetan yang perlu dibuang supaya rentetan yang tinggal menjadi palindrom.

Algoritma

• Buat fungsi yang dipanggil isPalindrome yang mengambil rentetan 's' sebagai parameter dan mengembalikan benar jika ia adalah palindrom, jika tidak ia mengembalikan palsu.

• Buat fungsi yang dipanggil minSizeSubstringToRemove yang mengambil rentetan 's' sebagai parameter.

• Mulakan pembolehubah 'MinSize' kepada panjang rentetan.

• Lelaran pada rentetan menggunakan gelung, menambah satu indeks 'i' daripada 0 kepada 'n'.

• Dalam setiap lelaran, lakukan langkah berikut −

• Cipta dua subrentetan dari permulaan rentetan hingga indeks 'i' dan satu lagi dari indeks 'i' hingga hujung rentetan.

• Semak sama ada mana-mana subrentetan adalah palindrom.

• Jika mana-mana subrentetan ialah palindrom, kemas kini 'minSize' kepada nilai minimum antara panjang substring bukan palindrom dan 'minSize'.

• Kembalikan 'MinSize' sebagai hasilnya.

Contoh

#include <iostream>
#include <string>
#include <algorithm>

// Function to check if a string is a palindrome
bool isPalindrome(const std::string &s) {
   int left = 0;
   int right = s.length() - 1;
   
   while (left < right) {
      if (s[left] != s[right]) {
         return false;
      }
      ++left;
      --right;
   }
   
   return true;
}

// Function to find the minimum size substring to be removed
int minSizeSubstringToRemove(std::string s) {
   int n = s.length();
   int minSize = n;
   
   for (int i = 0; i <= n; ++i) {
      std::string leftSubstring = s.substr(0, i);
      std::string rightSubstring = s.substr(i, n - i);
   
      if (isPalindrome(leftSubstring)) {
         minSize = std::min(minSize, static_cast<int>(rightSubstring.length()));
      }
      if (isPalindrome(rightSubstring)) {
         minSize = std::min(minSize, static_cast<int>(leftSubstring.length()));
      }
   }
   
   return minSize;
}

int main() {
   std::string s = "abccbaab";
   int result = minSizeSubstringToRemove(s);
   std::cout << "Minimum size substring to be removed: " << result << std::endl;
   
   return 0;
}

Output

Minimum size substring to be removed: 2

Contoh kes ujian

Pertimbangkan rentetan berikut: "abccbaab". Substring yang mungkin dan keadaan palindromik yang sepadan adalah seperti berikut:

• Subrentetan kiri = "", substring kanan = "abccbaab", palindrom = palsu

• Subrentetan kiri = "a", substring kanan = "bccbaab", palindrom = palsu

• Subrentetan kiri = "ab", substring kanan = "ccbaab", palindrom = palsu

• Subrentetan kiri = "abc", substring kanan = "cbaab", palindrom = palsu

• Subrentetan kiri = "abcc", substring kanan = "baab", palindrom = palsu

• Subrentetan kiri = "abccb", substring kanan = "aab", palindrom = benar (subrentetan kiri)

• Subrentetan kiri = "abccba", substring kanan = "ab", palindrom = benar (substring kiri)

• Subrentetan kiri = "abccbaa", substring kanan = "b", palindrom = palsu

• Subrentetan kiri = "abccbaab", substring kanan = "", palindrom = palsu

Daripada lelaran di atas, kita dapat melihat bahawa saiz minimum subrentetan untuk dipadamkan ialah 2, yang berlaku apabila subrentetan kiri ialah "abccba" dan substring kanan ialah "ab". Dalam kes ini, memadamkan subrentetan kanan "ab" akan menjadikan rentetan yang tinggal "abccba" sebagai palindrom.

Kesimpulan

Dalam artikel ini, kami meneroka masalah mencari subrentetan saiz minimum yang mesti dikeluarkan untuk menjadikan rentetan tertentu sebagai palindrom. Kami menyediakan pelaksanaan C++ yang jelas dan cekap yang menggunakan gelung mudah untuk mengulangi rentetan, mencipta subrentetan dan menyemak status palindromnya untuk mencari saiz minimum subrentetan yang mesti dialih keluar.

Dengan memahami algoritma ini, anda boleh menggunakan konsep yang serupa untuk menyelesaikan masalah manipulasi rentetan dan palindrom lain dalam sains komputer dan pengaturcaraan.

Atas ialah kandungan terperinci Subrentetan terkecil yang perlu dikeluarkan untuk menjadikan rentetan yang diberikan sebagai palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!