Số Append tối thiểu cần thiết để tạo chuỗi palindrome trong C ++

Tuyên bố vấn đề

Cho một chuỗi, hãy tìm các ký tự tối thiểu được thêm vào để tạo thành một chuỗi palindrome.

Ví dụ

Nếu chuỗi là abcac thì chúng ta có thể tạo chuỗi palindrome bằng cách thêm 2 ký tự được căn lề cao tức là abcacba

Thuật toán

• Kiểm tra xem chuỗi đã là palindrome chưa, nếu có thì không cần thêm bất kỳ ký tự nào.
• Từng người một xóa một ký tự khỏi chuỗi và kiểm tra xem chuỗi còn lại có phải là palindrome hay không
• Lặp lại quy trình trên cho đến khi chuỗi trở nên nhạt màu
• Trả lại số ký tự đã loại bỏ cho đến nay làm câu trả lời cuối cùng

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 << "Characters to be appended = " << requiredAppends(str) << endl;
   return 0;
}

Đầu ra

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 -

Characters to be appended = 2