Chương trình đếm số lượng xâu đối xứng sau khi tách tối thiểu trong C++

Mô tả bài toán

Cho một xâu chữ thường s, tách nó thành ít xâu con nhất sao cho mỗi xâu con là một xâu đối xứng (palindrome). Trả về số lượng xâu con đó.

Ví dụ: s = "levelracecar" → kết quả 2 (tách thành "level" và "racecar").

Giải thuật

1. n := độ dài xâu A.
2. Tạo mảng result kích thước n+1, result[n] = -1.
3. Duyệt i từ n-1 xuống 0:
   • result[i] = n - i - 1.
   • Duyệt j từ i đến n-1:
     • Nếu xâu con A[i..j] là palindrome thì result[i] = min(result[i], 1 + result[j+1]).
4. Trả về result[0] + 1.

Ví dụ minh họa (C++)

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

class Solution {
public:
    bool isPalindrome(string A) {
        int left = 0, right = A.size() - 1;
        while (left < right) {
            if (A[left] != A[right]) return 0;
            left++; right--;
        }
        return 1;
    }
    int solve(string A) {
        int n = A.size();
        vector<int> result(n + 1);
        result[n] = -1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = n - i - 1;
            for (int j = i; j < n; j++) {
                if (isPalindrome(A.substr(i, j - i + 1))) {
                    result[i] = min(result[i], 1 + result[j + 1]);
                }
            }
        }
        return result[0] + 1;
    }
};

int solve(string s) {
    return (new Solution())->solve(s);
}

int main() {
    string s = "levelracecar";
    cout << solve(s);
    return 0;
}

Đầu vào

"levelracecar"

Đầu ra

2