Palindrome Partitioning (การแบ่งสตริงเป็นพาลินโดรมน้อยที่สุด)

กำหนดสตริง ต้องการหา จำนวนครั้งน้อยที่สุด (Minimum Cuts) ในการตัดสตริง ทำให้ทุกชิ้นเป็นพาลินโดรม

ตัวอย่าง Input และ Output

Input: "ababbbabbababa"
Output: Min cuts for Palindrome Partitioning is: 3
Palindromes: a | babbbab | b | ababa

อัลกอริทึม Dynamic Programming

ฟังก์ชัน minPalPart(str)

ใช้ 2 ตาราง:

• pal[i][j]: true ถ้า str[i..j] เป็นพาลินโดรม
• cut[i][j]: minimum cuts สำหรับ str[i..j]

ขั้นตอน:

1. Base case: pal[i][i] = true, cut[i][i] = 0 (ตัวเดียว)
2. for len = 2 ถึง n:
   • for i = 0 ถึง n-len:
     • j = i + len - 1
     • เช็คพาลินโดรม:
       • len=2: pal[i][j] = (str[i] == str[j])
       • len>2: pal[i][j] = (str[i]==str[j]) && pal[i+1][j-1]
     • คำนวณ cut:
       • ถ้า pal[i][j] → cut[i][j] = 0
       • มิฉะนั้น: cut[i][j] = min over k (cut[i][k] + cut[k+1][j] + 1) สำหรับ k = i ถึง j-1
3. คืน cut[0][n-1]

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

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

int minPalPartion(string str) {
    int n = str.size();
    int cut[n][n];
    bool pal[n][n];

    for (int i = 0; i < n; i++) {
        pal[i][i] = true;
        cut[i][i] = 0;
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n-len+1; i++) {
            int j = i + len - 1;
            if (len == 2)
                pal[i][j] = (str[i] == str[j]);
            else
                pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];

            if (pal[i][j])
                cut[i][j] = 0;
            else {
                cut[i][j] = INT_MAX;
                for (int k = i; k <= j-1; k++)
                    cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j] + 1);
            }
        }
    }
    return cut[0][n-1];
}

int main() {
    string str = "ababbbabbababa";
    cout << "Min cuts for Palindrome Partitioning is: " << minPalPartion(str);
    return 0;
}

Output

Min cuts for Palindrome Partitioning is: 3

ความซับซ้อน

• Time: O(n³) - len, i, k ทั้งสามลูป
• Space: O(n²)

การเพิ่มประสิทธิภาพเป็น O(n²)

คำนวณ cut[i] = min cuts สำหรับ prefix str[0..i] แทน: cut[i] = min(cut[j-1] + 1) สำหรับ j ที่ str[j..i] เป็นพาลินโดรม (ใช้ pal table เช็ค O(1))