C++ Program: หาจำนวนวิธี Partition คำ ให้แต่ละส่วนเป็น Palindrome

โจทย์: หา ทั้งหมด วิธีการแบ่ง String ให้ทุก Substring เป็น Palindrome (อ่านซ้าย-ขวาและขวา-ซ้ายเหมือนกัน) ใช้ Backtracking (DFS) สำรวจทุกความเป็นไปได้

Algorithm: Backtracking

1. เริ่มจาก Index 0
2. ลองตัด Substring ทุกความยาวเริ่มจาก Index ปัจจุบัน
3. ถ้า Substring นั้นเป็น Palindrome → เพิ่มลง Path และ Recurse ต่อจาก Index ถัดไป
4. ถ้าถึงท้าย String → บันทึก Path นี้เป็นหนึ่ง Solution
5. Backtrack: ลบ Substring สุดท้ายออกจาก Path แล้วลองตัดแบบอื่น

ฟังก์ชันตรวจสอบ Palindrome

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

โค้ดสมบูรณ์ (Backtracking)

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

void partitionHelper(const string& s, int start, 
                     vector& current,
                     vector>& result) {
    int n = s.length();
    
    // Base Case: ถึงท้าย String
    if (start == n) {
        result.push_back(current);
        return;
    }
    
    // ลองตัด Substring ทุกความยาวจาก start
    for (int end = start; end < n; end++) {
        if (isPalindrome(s, start, end)) {
            current.push_back(s.substr(start, end - start + 1));
            partitionHelper(s, end + 1, current, result);
            current.pop_back(); // Backtrack
        }
    }
}

vector> palindromePartitioning(const string& s) {
    vector> result;
    vector current;
    partitionHelper(s, 0, current, result);
    return result;
}

void printPartitions(const vector>& parts) {
    for (const auto& partition : parts) {
        for (const auto& word : partition) {
            cout << word << " ";
        }
        cout << '\n';
    }
}

int main() {
    string s = "tutorials";
    auto partitions = palindromePartitioning(s);
    
    cout << "All palindromic partitions of \"" << s << "\":\n";
    printPartitions(partitions);
    cout << "Total: " << partitions.size() << " ways\n";
    
    return 0;
}

ผลลัพธ์สำหรับ "tutorials"

All palindromic partitions of "tutorials":
t u t o r i a l s
t u t o r i a l s
tut o r i a l s
... (partitions อื่นๆ)
Total: X ways

หมายเหตุ: "tutorials" มี Palindromic Partitions หลายวิธี เช่น "t u t o r i a l s" (ทุกตัวอักษร), "tut o r i a l s" เป็นต้น

Optimization: DP + Backtracking

Pre-compute Palindrome Table O(N²) แล้ว Backtracking เร็วขึ้น

// Precompute isPal[i][j] = true if s[i..j] is palindrome
vector> buildPalTable(const string& s) {
    int n = s.length();
    vector> dp(n, vector(n, false));
    
    for (int i = 0; i < n; i++) dp[i][i] = true;           // Length 1
    for (int i = 0; i < n-1; i++) dp[i][i+1] = (s[i]==s[i+1]); // Length 2
    
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
        }
    }
    return dp;
}

Complexity

• Time: O(N × 2^N) Worst Case (ทุก Substring เป็น Palindrome เช่น "aaaa")
• Space: O(N) Recursion Stack + O(N²) Output Storage
• DP Precompute: O(N²) Time, O(N²) Space

โจทย์ที่เกี่ยวข้อง (LeetCode)

• 131. Palindrome Partitioning - หา All Partitions (นี้แหละ)
• 132. Palindrome Partitioning II - หา Minimum Cuts (DP Only)