แยกสตริง 2 สตริงให้เป็น Palindrome ใน C++

โจทย์

กำหนด 2 สตริง a และ b ความยาวเท่ากัน ตัดทั้งคู่ที่ตำแหน่งเดียวกัน (index i) ได้ 2 ส่วน: Prefix และ Suffix ตรวจสอบว่า:

• a[0..i] + b[i+1..n-1] เป็น Palindrome
• หรือ b[0..i] + a[i+1..n-1] เป็น Palindrome

ถ้าเจอ index ใด index หนึ่งที่ทำให้เป็น Palindrome → Return True

ตัวอย่าง

Input: a = "abcdef", b = "fedcba"

ตัดที่ index 2: abc|def และ fed|cba

abc + cba = abccba → Palindrome ✓ → True

แนวคิด: Two Pointers

ใช้ 2 pointers: left (หน้า), right (หลัง) เดินเข้ามาเรื่อยๆ จนเจอตัวอักษรไม่ตรง → ตรงนั้นคือจุดที่อาจต้อง "สลับ" สตริง

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(const string& s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++; r--;
    }
    return true;
}

bool checkSplit(const string& a, const string& b) {
    int n = a.size();
    int l = 0, r = n - 1;
    
    // หาจุดแรกที่ไม่ตรง
    while (l < r && a[l] == b[r]) {
        l++; r--;
    }
    
    // ถ้าเดินจนจบ → เป็น Palindrome แล้ว
    if (l >= r) return true;
    
    // ลองตัดที่จุด l..r: ตรวจสอบส่วนกลางของ a หรือ b
    return isPalindrome(a, l, r) || isPalindrome(b, l, r);
}

bool checkPalindromic(string a, string b) {
    if (a.size() < 2) return true;
    return checkSplit(a, b) || checkSplit(b, a);
}

int main() {
    string a = "abcpqr";
    string b = "mnocba";
    
    cout << (checkPalindromic(a, b) ? "True" : "False") << endl; // True
    
    // Test cases เพิ่ม
    cout << checkPalindromic("abcdef", "fedcba") << endl; // True
    cout << checkPalindromic("eatable", "tableau") << endl; // False
    cout << checkPalindromic("a", "b") << endl; // True
    
    return 0;
}

อธิบายอัลกอริทึม

1. checkSplit(a, b): เดิน two pointers จากนอกเข้าด้านใน จนกว่า a[l] != b[r]
2. ส่วนที่เหลือ [l..r] ต้องเป็น Palindrome ใน a หรือ b ก็พอ
3. checkPalindromic: ลองสลับบทบาท checkSplit(a,b) หรือ checkSplit(b,a)

Complexity

• Time: O(n) - ผ่านสตริงเพียงไม่กี่ครั้ง
• Space: O(1) - ไม่ใช้พื้นที่เพิ่ม (ยกเว้น Recursion stack ของ isPalindrome)

ผลลัพธ์

True
True
False
True

สรุป

Two-pointer technique ลดปัญหาจาก O(n²) เหลือ O(n) โดยหาจุด "แรกที่ไม่ตรง" แล้วตรวจสอบส่วนกลางว่าเป็น Palindrome เองหรือไม่