แนวคิด
เมื่อได้รับ string ให้หา palindrome ที่ยาวที่สุดที่สามารถสร้างได้โดยการลบหรือสลับตัวอักษรจาก string สุดท้ายคืนค่า palindrome เพียงอันเดียวถ้าพบว่ามี palindrome strings หลายอันที่มีความยาวสูงสุด
อินพุต
pqr
เอาต์พุต
p OR q OR r
อินพุต
ppqqrr
เอาต์พุต
pqrrqp OR qprrpq OR rqppqr OR palindromic string อื่นๆ ที่มีความยาว 6
อินพุต
pqp
เอาต์พุต
pqp
วิธีการ
ที่นี่ เราสามารถแบ่ง palindromic string ใดๆ ออกเป็น 3 ส่วน – beg, mid และ end สำหรับ palindromic string ความยาวคี่เช่น 2n + 1 ที่นี่ 'beg' ประกอบด้วย n ตัวอักษรแรกของ string 'mid' ประกอบด้วยแค่ 1 ตัวอักษร คือ (n + 1)th character และ 'end' ประกอบด้วย n ตัวอักษรสุดท้ายของ palindromic string สำหรับ palindromic string ความยาวคู่ 2n จะมี 'mid' ว่างเสมอ เรารู้แล้วว่า 'end' จะเป็น reverse ของ 'beg' สำหรับลำดับสำหรับ string ให้เป็น palindrome ตอนนี้แนวคิดคือนำการสังเกตข้างต้นมาใช้ใน solution เนื่องจากอนุญาตให้สลับตัวอักษรได้ ลำดับของตัวอักษรใน input string จึงไม่สำคัญ ตอนนี้เราหา frequency ของแต่ละตัวอักษรใน input string ก่อน หลังจากนั้นตัวอักษรทั้งหมดที่มี occurrence แบบคู่ (เช่น 2n) ใน input string จะเป็นส่วนหนึ่งของ output string เพราะเราสามารถวาง n ตัวอักษรใน 'beg' string และอีก n ตัวอักษรใน 'end' string ได้ง่ายๆ (ด้วยการรักษาลำดับ palindromic) สำหรับตัวอักษรที่มี occurrence แบบคี่ (เช่น 2n + 1) ที่นี่ เราเติม 'mid' ด้วยหนึ่งในตัวอักษรทั้งหมดเช่นนี้ และ 2n ตัวอักษรที่เหลือถูกแบ่งครึ่งและเพิ่มที่ต้นและท้าย
ตัวอย่างโค้ด
// โปรแกรม C++ เพื่อหา palindrome ที่ยาวที่สุดโดยการลบ // หรือสลับตัวอักษรจาก string ที่กำหนด #include <bits/stdc++.h> using namespace std; // ฟังก์ชันแสดงการหา palindrome ที่ยาวที่สุดโดยการลบ // หรือสลับตัวอักษรจาก string ที่กำหนด string findLongestPalindrome(string str1){ // แสดงการเก็บ freq ของตัวอักษรใน string int count1[256] = { 0 }; // หา freq ของตัวอักษรใน input string for (int i = 0; i < str1.size(); i++) count1[str1[i]]++; // แสดง palindromic string ใดๆ ที่ประกอบด้วย 3 ส่วน // beg1 + mid1 + end1 string beg1 = "", mid1 = "", end1 = ""; // วิธีแก้สมมติว่ามีแต่ lowercase characters ใน // string เราสามารถขยายได้ง่ายๆ // เพื่อพิจารณาชุดตัวอักษรใดๆ for (char ch1 = 'a'; ch1 <= 'z'; ch1++){ // ตอนนี้ถ้า current character freq เป็นคี่ if (count1[ch1] & 1){ // ที่นี่ mid1 จะมีแค่ 1 ตัวอักษร มัน // จะถูก override ด้วยตัวอักษรถัดไป // ที่มี odd freq mid1 = ch1; // ที่นี่ลด character freq ลงเพื่อทำ // ให้เป็นคู่และพิจารณาตัวอักษรปัจจุบัน // อีกครั้ง count1[ch1--]--; } // ที่นี่ถ้า current character freq เป็นคู่ else{ // ตอนนี้ถ้า count เป็น n(เลขคู่) push // n/2 ตัวอักษรไป beg string และที่เหลือ // n/2 ตัวอักษรจะเป็นส่วนหนึ่งของ end // string for (int i = 0; i < count1[ch1]/2 ; i++) beg1.push_back(ch1); } } // ที่นี่ end จะเป็น reverse ของ beg end1 = beg1; reverse(end1.begin(), end1.end()); // ตอนนี้คืนค่า palindrome string return beg1 + mid1 + end1; } // โค้ดหลัก int main(){ string str1 = "pqqprrs"; cout << findLongestPalindrome(str1); return 0; }เอาต์พุต
pqrsrqp
