ตรวจสอบ String เป็น Rotation ของ Palindrome ใน C++

ในบทความนี้จะตรวจสอบว่า String เป็น Palindrome หลัง Rotation หรือไม่ Palindrome คือ String ที่อ่านจากหน้าหลังได้เหมือนกัน String Rotation เป็น Palindrome เช่น "AAAAD" ไม่ใช่ Palindrome โดยตรง แต่ Rotation "AADAA" เป็น Palindrome

วิธีตรวจสอบ: เช็ค Palindrome ก่อน แล้ว Rotate ทีละ Character เช็คใหม่ ทำ n ครั้ง (n = ความยาว String)

ตัวอย่างโค้ด C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isPalindromeRange(string str, int left, int right) {
    return (left >= right) || (str[left] == str[right] && isPalindromeRange(str, left + 1, right - 1));
}

bool isRotatedPalindrome(string str) {
    int len = str.length();
    for (int i = 0; i < len; i++) {
        rotate(str.begin(), str.begin() + 1, str.end());
        if (isPalindromeRange(str, 0, len - 1))
            return true;
    }
    return false;
}

int main() {
    string str = "AAAAD"; // AADAA is palindrome
    if (isRotatedPalindrome(str))
        cout << "Its rotation is palindrome";
    else
        cout << "Its rotation is not palindrome";
}

ผลลัพธ์

Its rotation is palindrome