จำนวนการลบขั้นต่ำเพื่อสร้างสตริง palindrome ใน C++

คำชี้แจงปัญหา

รับสตริงขนาด 'n' งานคือการลบจำนวนอักขระขั้นต่ำเพื่อสร้างสตริง palindrome

หากสตริงที่ระบุคือ “abcda” เราสามารถลบอักขระ 2 ตัว ยกเว้นตัวแรกและตัวสุดท้ายเพื่อทำให้เป็นพาลินโดรม

หากเราลบอักขระ 'b' และ 'c' สตริง "ada" จะเป็น palindrome
หากเราลบอักขระ 'c' และ 'd' สตริง "aba" จะเป็น palindrome
หากเราลบอักขระ 'b' และ 'd' สตริง "aca" จะเป็น palindrome

อัลกอริทึม

<ก่อน>1. ค้นหาลำดับย่อย palindromic ที่ยาวที่สุดของสตริงที่กำหนด เรียกมันว่า “lpsSize”.2. อักขระขั้นต่ำที่จะลบ =(ความยาวของสตริง – lpsSize) รหัส

ตัวอย่าง

#include #include using namespace std;int lps(string s, int i, int j){ if (i ==j) { return 1; } if (s[i] ==s[j] &&i + 1 ==j) { return 2; } if (s[i] ==s[j]) { return lps(s, i + 1, j - 1) + 2; } คืนค่า max(lps(s, i, j - 1), lps(s, i + 1, j));}int minDeletion(string s){ int n =s.size(); int lpsSize =lps(s, 0, n); return (n - lpsSize);}int main(){ cout <<"อักขระขั้นต่ำที่จะลบ =" < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 อักขระขั้นต่ำที่จะลบ =2