LeetCode: Palindrome Partitioning II

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.

---

The problem can be transformed to the following: minimum[i:n] means the minimum cut we needed for substring s[i:n], and it could be the minimum of minimum[j+1:n]+1 for all i <= j < n.

C++ Code:

/*
 * func: min_cut
 * goal: find the minimum number of min_cut so that each partition is a palindrome
 * @param s: input string
 * return: minimum cut
 */
int min_cut(string s){
    size_t str_length = s.length();
    if(str_length == 0){
        return 0;
    }
    //a 2D array which indicate if substring(i, j) is a palindrome
    vector<vector<bool> > palindrome(str_length, vector<bool>(str_length, false));
    for(int i = 0; i < str_length; ++i){
        //Check palindrome taking s[i] as symmetry axis
        int left = i;
        int right = i;
        while(left >= 0 && right < str_length && s[left] == s[right]){
            palindrome[left][right] = true;
            --left;
            ++right;
        }
        //Check palindrome taking s[i] s[i+1] as symmetry axis
        left = i;
        right = i+1;
        while(left >= 0 && right < str_length && s[left] == s[right]){
            palindrome[left][right] = true;
            --left;
            ++right;
        }
    }
    vector<int> minimum_cut(str_length, str_length);
    for(int i = 0; i < str_length; ++i){
        if(palindrome[0][i]){
            minimum_cut[i] = 0;
        }else{
            int min_cut_now = str_length;
            for(int j = 1; j <= i; ++j){
                if(palindrome[j][i] && min_cut_now > minimum_cut[j-1] + 1){
                    min_cut_now = minimum_cut[j-1] + 1;
                }
            }
            minimum_cut[i] = min_cut_now;
        }
    }
    return minimum_cut.back();
}

Python Code:

# func: find the minimum cut needed for a palindrome partitioning of string
# @param s: input string
# @return: minimum cut
def min_cut(s):
    if not s:
        return 0
    palindrome = [[False] * len(s) for _ in xrange(len(s))]
    minimum_cut = [len(s) - i for i in xrange(len(s)+1)]
    for i in xrange(len(s)-1, -1, -1):
        for j in xrange(i, len(s)):
            if s[i] == s[j] and (j-i < 2 or palindrome[i+1][j-1]):
                palindrome[i][j] = True
                minimum_cut[i] = min(minimum_cut[i], minimum_cut[j+1] + 1)

    return minimum_cut[0]-1

Reference Link:

1. 水中的鱼: [LeetCode] Palindrome Partitioning II, Solution: http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning-ii.html