คำชี้แจงปัญหา
ระบุสตริง ให้ค้นหาอักขระขั้นต่ำที่จะต่อท้ายเพื่อสร้างสตริงพาลินโดรม
ตัวอย่าง
หาก string เป็น abcac เราก็สามารถสร้าง string palindrome ได้โดยการต่อท้ายอักขระที่ไฮไลต์ไว้ 2 ตัว นั่นคือ abcacba
อัลกอริทึม
- ตรวจสอบว่า string เป็น palindrome อยู่แล้วหรือไม่ ถ้าใช่ ไม่จำเป็นต้องต่อท้ายอักขระใดๆ
- นำอักขระออกจากสตริงทีละตัวและตรวจสอบว่าสตริงที่เหลือเป็น palindrome หรือไม่
- ทำซ้ำขั้นตอนข้างต้นจนกว่าสตริงจะกลายเป็น palidrome
- ส่งคืนจำนวนอักขระที่ถูกลบจนถึงคำตอบสุดท้าย
ตัวอย่าง
#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
