[leetcode]132. Palindrome Partitioning II

Problem
Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution

enumerate the length of the last part partition which is a palindrome.

If we pre-calculate the array f[i][j] which means whether string[i...j] is a palindrome. 

    f[i][j] = f[i + 1][j - 1] && str[i] == str[j] where len >= 2

    f[i][j] = str[i] == str[j] where len < 2

let dp[i] means the mininum cuts of string[0...i], thus 

    dp[i] = 0 if string[0...i] is a palindrome itself.

    dp[i] = min(dp[j] + 1) where 1 <= j <= i   and string[i...j] is a palindrome.

Code

class Solution {
public:
 int minCut(string s) {
        int n = s.size();
        vector > f(n + 1,vector(n + 1,false));
        for (int len = 1;len <= n;len ++) {
            for (int i = 0;i + len - 1 < n;i ++) {
                int j = i + len - 1;
                if (s[i] == s[j] && (len <= 2 || f[i + 1][j - 1])) {
                    f[i][j] = true;
                }
                else {
                    f[i][j] = false;
                }
            }
        }
        cout << f[0][1] << endl;
        vector dp(n + 1,0x3f3f3f3f);
        for (int i = 0;i < n;i ++) {
            if (f[0][i]) dp[i] = 0;
            else {
                for (int j = 1;j <= i;j ++) {
                    if (f[j][i]) {
                        dp[i] = min(dp[i],dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 2];
 }
};