Semak sama ada subrentetan tiga rentetan yang diberikan boleh digabungkan menjadi rentetan palindrom

Palindrom ialah topik yang menarik dalam sains komputer dan pengaturcaraan. Palindrom ialah urutan perkataan, frasa, nombor atau aksara lain yang dibaca sama dari hadapan ke belakang seperti dari belakang ke hadapan, mengabaikan ruang, tanda baca dan huruf besar. Dalam artikel ini, kita akan mengkaji masalah unik: bagaimana untuk menentukan sama ada subrentetan daripada tiga rentetan yang diberikan boleh digabungkan untuk membentuk palindrom. Soalan ini ialah soalan temu bual biasa dan boleh diselesaikan menggunakan pelbagai teknik, termasuk manipulasi rentetan, pencincangan dan pengaturcaraan dinamik.

Pernyataan Masalah

Memandangkan tiga rentetan, tugasnya adalah untuk menyemak sama ada boleh memilih subrentetan daripada setiap rentetan yang diberikan dan menggabungkannya untuk membentuk palindrom.

Kaedah

Pendekatan umum untuk menyelesaikan masalah ini melibatkan langkah-langkah berikut -

• Sambungkan tiga rentetan dalam enam cara berbeza (semua pilih atur tiga rentetan).

• Untuk setiap rentetan bercantum, semak sama ada ia boleh membentuk palindrom.

Untuk menyemak sama ada rentetan boleh membentuk palindrom, kita perlu memastikan bahawa tidak lebih daripada satu aksara muncul dengan frekuensi ganjil dalam rentetan.

Penyelesaian C++

Contoh

Ini adalah fungsi C++ yang melaksanakan kaedah di atas −

#include<bits/stdc++.h>
using namespace std;

bool canFormPalindrome(string str) {
   vector<int> count(256, 0);
   for (int i = 0; str[i]; i++)
      count[str[i]]++;
   int odd = 0;
   for (int i = 0; i < 256; i++) {
      if (count[i] & 1)
         odd++;
      if (odd > 1)
         return false;
   }
   return true;
}

bool checkSubstrings(string s1, string s2, string s3) {
   string arr[] = {s1, s2, s3, s1, s3, s2};
   for (int i = 0; i < 3; i++) {
      if (canFormPalindrome(arr[i] + arr[i + 1] + arr[i + 2]))
         return true;
   }
   return false;
}

int main() {
   string s1 = "abc";
   string s2 = "def";
   string s3 = "cba";
   if (checkSubstrings(s1, s2, s3))
      cout << "Yes\n";
   else
      cout << "No\n";
   return 0;
}

Output

No

Contoh keterangan kes ujian

Mari kita buat rentetan "abc", "def" dan "cba".

Fungsi bolehFormPalindrome(str) menyemak sama ada keseluruhan rentetan boleh disusun semula menjadi palindrom, bukannya menyemak sama ada ia sudah menjadi palindrom.

Menggunakan rentetan "abc", "de" dan "edcba", rentetan "abcdeedcba" yang diperoleh dengan menggabungkannya tidak boleh disusun semula menjadi palindrom kerana ia mempunyai dua aksara 'd' dan dua aksara 'e', ​​tetapi hanya satu ' watak b. Oleh itu, output sememangnya "Tidak".

Fungsi checkSubstrings menyemak semua kemungkinan gabungan tiga rentetan. Walau bagaimanapun, tiada satu pun daripada ini boleh disusun semula untuk membentuk palindrom, jadi outputnya ialah "Tidak".

Kesimpulan

Dapat menyelesaikan soalan sedemikian bukan sahaja membantu dalam melakukan temu duga pengekodan dengan baik tetapi juga meningkatkan kemahiran menyelesaikan masalah yang penting untuk setiap jurutera perisian. Soalan ini ialah contoh yang baik tentang cara menggunakan manipulasi rentetan dan pencincangan untuk menyelesaikan masalah yang kompleks. Latihan dan pemahaman adalah kunci untuk menguasai topik ini.

Atas ialah kandungan terperinci Semak sama ada subrentetan tiga rentetan yang diberikan boleh digabungkan menjadi rentetan palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!