ข้อความโจทย์
กำหนดสตริง หาตัวอักษรน้อยที่สุดที่ต้องต่อท้ายเพื่อทำให้สตริงเป็นพาลินโดรม
ตัวอย่าง
ถ้าสตริงคือ abcac เราสามารถทำให้เป็นพาลินโดรมได้โดยการต่อท้าย 2 ตัวอักษรที่ไฮไลท์ คือ abcacba
อัลกอริทึม
- ตรวจสอบว่าสตริงเป็นพาลินโดรมอยู่แล้วหรือไม่ ถ้าใช่ ไม่ต้องต่อท้ายอะไร
- ทีละตัว นำตัวอักษรออกจากสตริง และตรวจสอบว่าสตริงที่เหลือเป็นพาลินโดรมหรือไม่
- ทำซ้ำขั้นตอนข้างต้นจนกว่าสตริงจะกลายเป็นพาลินโดรม
- คืนค่าจำนวนตัวอักษรที่นำออกไปจนถึงตอนนั้นเป็นคำตอบสุดท้าย
ตัวอย่าง
#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; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้
Characters to be appended = 2
