Đề bài
Cho một chuỗi kích thước 'n'. Nhiệm vụ là xóa số lượng ký tự tối thiểu để chuỗi trở thành palindrome.
Nếu chuỗi cho trước là "abcda" thì chúng ta có thể xóa bất kỳ 2 ký tự nào trừ ký tự đầu và cuối để làm cho nó thành palindrome.
- Nếu xóa ký tự 'b' và 'c' thì chuỗi "ada" là palindrome
- Nếu xóa ký tự 'c' và 'd' thì chuỗi "aba" là palindrome
- Nếu xóa ký tự 'b' và 'd' thì chuỗi "aca" là palindrome
Thuật toán
1. Tìm dãy con palindrome dài nhất của chuỗi cho trước. Gọi nó là "lpsSize". 2. Số ký tự tối thiểu cần xóa = (độ dài chuỗi – lpsSize)
Ví dụ
#include <iostream> #include <algorithm> 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; } return 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 << "Minimum characters to be deleted = " << minDeletion("abcda") << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum characters to be deleted = 2