การแบ่งพาลินโดรมน้อยที่สุดใน C++ (Palindrome Partitioning II)

ภาพรวมปัญหา

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

ตัวอย่าง

"ababba" → 2 ครั้ง (aba|bb|a)

วิธีแก้ปัญหา: DP + Palindrome Check

res[i] = ตัดน้อยที่สุดจาก index i ถึงท้าย
res[n] = -1 (base)
res[i] = min(1 + res[j+1]) สำหรับทุก j ที่ s[i..j] เป็นพาลินโดรม

โค้ด C++

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

bool isPalindrome(string A) {
    int l = 0, r = A.size()-1;
    while (l < r) if (A[l++] != A[r--]) return false;
    return true;
}

int solve(string A) {
    int n = A.size();
    vector<int> res(n+1);
    res[n] = -1;
    for (int i = n-1; i >= 0; i--) {
        res[i] = n - i - 1;
        for (int j = i; j < n; j++)
            if (isPalindrome(A.substr(i, j-i+1)))
                res[i] = min(res[i], 1 + res[j+1]);
    }
    return res[0];
}

class Solution {
public:
    int minCut(string s) { return solve(s); }
};

int main() {
    Solution ob;
    cout << (ob.minCut("ababba"));
}

ผลลัพธ์

2

การวิเคราะห์ความซับซ้อน

• เวลา: O(n³) — n² substring × n palindrome check
• พื้นที่: O(n)

การปรับปรุง

Precompute palindrome table O(n²) → รวม O(n²)