Palindrome Partitioning II

Description

Given a string s, cut s into some substrings such that every substring is a palindrome.

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

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

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param s a string
     * @return an integer
     */
    int minCut(string s) {
        // write your code here
        if (s.empty()) {
            return 0;
        }
        int n = s.size();
        // pre-calculation all possible palinfrome
        vector<vector<bool>> allpalindrome(n, vector<bool>(n, false));
        find_allpalindrome(s, allpalindrome);
        // initialization dp
        vector<int> dp(n+1, 0);
        // for abcd, length = 4, atmost we can use length-1 cut to divide palindrome
        for (int i = 0; i <= n; ++i) {
            dp[i] = i-1;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (allpalindrome[j][i-1]) {
                    dp[i] = min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[n];
    }
private:
    // bool isPalindrome(string& s, int start, int end) {
    //     // if (s.empty()) {
    //     //     return true;
    //     // }
    //     //int n = s.size();
    //     for (int i = start, j = end; i < j; ++i, --j) {
    //         if (s[start] != s[end]) {
    //             return false;
    //         }
    //     }
    //     return true;
    // }
    void find_allpalindrome(string& s, vector<vector<bool>>& allpalindrome) {
        int imax = allpalindrome.size();
        // for one letter, it is palindrome
        for (int i = 0; i < imax; ++i) {
            allpalindrome[i][i] = true;
        }
        // for two letters
        for (int i = 0; i < imax-1; ++i) {
            allpalindrome[i][i+1] = (s[i] == s[i+1]);
        }
        // for three letters or more
        // substring length: [start, +1,....+len = len +1]
        for (int len = 2; len < imax; ++len) {
            for (int start = 0; start+len < imax; ++start) {
               allpalindrome[start][start+len] = 
                    allpalindrome[start+1][start+len-1] 
                    && (s[start] == s[start+len]);
            }
        }
        return; 
    }
};

Similar problems

x

Tags

x