C++: Tìm số cách phân hoạch chuỗi thành các palindrome

Bài toán: Cho một chuỗi, đếm và liệt kê tất cả các cách phân hoạch (partition) chuỗi thành các chuỗi con sao cho mỗi chuỗi con là một palindrome (đối xứng).

Thuật toán: Backtracking (Quay lui)

Duyệt từ trái sang phải, tại mỗi vị trí thử tất cả các chuỗi con bắt đầu tại vị trí đó. Nếu chuỗi con là palindrome, thêm vào partition hiện tại và đệ quy tiếp tục từ vị trí tiếp theo.

Kiểm tra Palindrome

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

Hàm đệ quy chính

void partitionHelper(const string& s, int start, 
                     vector& current, 
                     vector>& result) {
    if (start == s.size()) {
        result.push_back(current); // Tìm được một partition hợp lệ
        return;
    }
    
    for (int end = start; end < s.size(); ++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
        }
    }
}

Chương trình hoàn chỉnh

#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;
    return true;
}

void partitionHelper(const string& s, int start, 
                     vector& current, 
                     vector>& result) {
    if (start == s.size()) {
        result.push_back(current);
        return;
    }
    for (int end = start; end < s.size(); ++end) {
        if (isPalindrome(s, start, end)) {
            current.push_back(s.substr(start, end - start + 1));
            partitionHelper(s, end + 1, current, result);
            current.pop_back();
        }
    }
}

vector> partition(string s) {
    vector> result;
    vector current;
    partitionHelper(s, 0, current, result);
    return result;
}

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

int main() {
    string s = "tutorials";
    auto parts = partition(s);
    cout << "So cach phan hoach: " << parts.size() << "\n\n";
    printPartitions(parts);
    return 0;
}

Kết quả cho "tutorials"

So cach phan hoach: 2

t u t o r i a l s
tut o r i a l s

Giải thích: Chuỗi "tutorials" chỉ có 2 cách phân hoạch thành palindrome: 1. Mỗi ký tự riêng lẻ (luôn là palindrome độ dài 1). 2. "tut" (palindrome) + các ký tự còn lại.

Tối ưu hóa: DP + Backtracking

Để tránh kiểm tra palindrome lặp lại, tiền tính bảng isPal[i][j] bằng DP:

// Tiền xử lý O(n^2)
vector> isPal(n, vector(n, false));
for (int i = n-1; i >= 0; --i) {
    for (int j = i; j < n; ++j) {
        isPal[i][j] = (s[i] == s[j]) && (j - i < 2 || isPal[i+1][j-1]);
    }
}
// Sau đó trong backtracking dùng isPal[start][end] thay vì gọi hàm kiểm tra

Độ phức tạp: Số partition có thể lớn (exponential), nhưng với chuỗi ngắn (< 20 ký tự) backtracking đủ nhanh.