Phân chia palindrome II (Palindrome Partitioning II) trong C++

Cho chuỗi s, cắt thành các chuỗi con palindrome. Tìm số lần cắt tối thiểu.

Ví dụ

s = "ababba" → Cắt: "aba|bb|a" → 2 lần cắt.

Thuật toán: DP + Kiểm tra palindrome

res[i] = số cắt tối thiểu cho chuỗi con .

• res[n] = -1 (cơ sở: chuỗi rỗng cần -1 cắt để công thức 1 + res[j+1] cho 0 cắt).
• Duyệt i từ n-1 xuống 0:
  • res[i] = n - i - 1 (cắt từng ký tự).
  • Với mỗi j từ i đến n-1: nếu là palindrome → res[i] = min(res[i], 1 + res[j+1]).

Kiểm tra palindrome

Hàm isPalindrome dùng 2 con trỏ left, right so sánh từ 2 đầu.

Cài đặt C++

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

bool isPalindrome(string A) {
    int left = 0, right = A.size() - 1;
    while (left < right) {
        if (A[left] != A[right]) return false;
        left++; right--;
    }
    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");
    return 0;
}

Độ phức tạp

• Thời gian: O(n^3) — O(n^2) cặp (i,j), mỗi lần check palindrome O(n).
• Không gian: O(n).

Tối ưu: Tiền tính bảng isPal[i][j] trong O(n^2) → tổng O(n^2).

Input / Output

Input:  "ababba"
Output: 2