回文串划分 Palindrome Partition

此题为动态规划。 问题描述看这里

转移方程式如下

// dp[i] = min{ dp[i - k] if (s[k] == s[i]) && (s[k+1..i-1] is palindrome) }, k = 0,1,2...i. dp[i]的初始值是一个很大的值

注意：任何重复判断回文串的方案都会造成超时。必须要缓存回文串判断的结果。

//.h

#include <string>

class PalindromePartition {
public:
    static void test();

    static int minCut(std::string &s);

    static bool isPalindrome(const std::string &s);

};

//.cpp
//
// Created on 3/14/18.
//

#include <iostream>
#include <vector>
#include "PalindromePartition.h"

using namespace std;

// dp[i] = min{dp[i - k] if (s[k] == s[i]) && (s[k+1..i-1] is palindrome) }, k = 0,1,2...i. dp[i]的初始值是一个很大的值
int PalindromePartition::minCut(std::string &s) {
    const int N = s.size();

    if (isPalindrome(s)) {
        return 0;
    }

    vector<vector<int>> mat(N, vector<int>(N, 0));

    for (int i = 0; i < N; i++) {
        mat[i][i] = 1;
    }

    vector<int> dp(N, 0);
    for (int i = 0; i < N; i++) {
        dp[i] = 0x0fffffff;
        for (int j = 0; j <= i; j++) {
            if ((s[j] == s[i])) {
                if (j + 1 <= i - 1) {
                    if (!mat[j+1][i-1]) {
                        continue;
                    }
                }
                mat[j][i] = 1;
                if (j - 1 >= 0) {
                    dp[i] = min(dp[i], dp[j - 1] + 1);
                } else {
                    dp[i] = 0;
                }
            }
        }

    }
    return dp[N - 1];
}

bool PalindromePartition::isPalindrome(const std::string &s) {
    if (s.size() <= 1) {
        return true;
    }

    const int N = s.size();
    for (int i = 0; i < N / 2; i++) {
        if (s[i] != s[N - i - 1]) {
            return false;
        }
    }
    return true;
}

void PalindromePartition::test() {
    vector<string> vec = {
            "abbab",
            "aab",
            "abccba",
            "abcabc",
            "aaabaaa",
            "aabcaa",
            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    };
    for (auto &s: vec) {
        cout << minCut(s) << endl;
    }
}