Số lần thêm ký tự tối thiểu để chuỗi thành palindrome trong C++

Đề bài

Cho một chuỗi, tìm số ký tự tối thiểu cần thêm vào cuối để chuỗi trở thành palindrome.

Ví dụ

Nếu chuỗi là abcac thì có thể làm palindrome bằng cách thêm 2 ký tự nổi bật: abcacba

Thuật toán

• Kiểm tra chuỗi đã là palindrome chưa, nếu có thì không cần thêm.
• Loại bỏ từng ký tự một từ chuỗi và kiểm tra chuỗi còn lại có phải palindrome không.
• Lặp lại cho đến khi chuỗi thành palindrome.
• Trả về số ký tự đã loại bỏ làm đáp án.

Ví dụ

#include <iostream>
#include <cstring>
using namespace std;
bool isPalindrome(char *str) {
    int n = strlen(str);
    if (n == 1) return true;
    int start = 0, end = n - 1;
    while (start < end) {
        if (str[start] != str[end]) return false;
        ++start;
        --end;
    }
    return true;
}
int requiredAppends(char *str) {
    if (isPalindrome(str)) return 0;
    return 1 + requiredAppends(str + 1);
}
int main() {
    char *str = "abcac";
    cout << "Ký tự cần thêm = " << requiredAppends(str) << 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:

Ký tự cần thêm = 2