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.

Analysis

核心：

• cut[i] 代表s的前i个字母至少需要cut多少次
• scan s，从某一个位置i的左右开始去找。当找到一个palindrome的时候，更新cut的值为前面不是palindrome的部分cut值+1，因为前面的已经算好，加上一个palindrome，多cut一次即可
• 最后返回cut[s.length]

Example: "aabbabc", return 3, aa | b | bab | c

        0   1   2   3   4   5   6   
        a   a   b   b   a   b   c
    -1  0   0   1   1   1   2   3

Initialize cut = [-1  0   1   2   3   4   5   6]

i=0: 
odd: "a" is palindrome, update cut[1] to min(0, -1+1)
even: "aa" is palindrome, update cut[2] to min(1, -1+1)
cut = [-1  0   0   2   3   4   5   6]

i=1:
odd: "a" is palindrome, update cut[2] to min(0, 0+1)
even: no palindrome
cut = [-1  0   0   2   3   4   5   6]

i=2:
odd: "b" is palindrome, update cut[3] to min(2, 0+1)
even: "bb" is palindrome, update cut[4] to min(3, 0+1)
      "abba" is palindrome, update cut[5] to min(4, 0+1)
cut = [-1  0   0   1   1   1   5   6]

i=3:
odd: "b" is palindrome, update cut[4] to min(1, 1+1)
even: no palindrome
cut = [-1  0   0   1   1   1   5   6]

i=4:
odd: "a" is palindrome, update cut[5] to min(1, 1+1)
even: "bab" is palindrome, update cut[6] to min(5, 1+1)
cut = [-1  0   0   1   1   1   2   6]

i=5:
odd: "b" is palindrome, update cut[6] to min(2, 1+1)
even: no palindrome
cut = [-1  0   0   1   1   1   2   6]

i=6:
odd: "c" is palindrome, update cut[7] to min(6, 2+1)
even: no palindrome
cut = [-1  0   0   1   1   1   2   3]

return cut[7]=3

Code

public class Solution {
    public int minCut(String s) {
        if (s==null || s.length()<=1) return 0;
        int len = s.length();

        //cut[i]: number of cuts for the first i chars
        int[] cut = new int[len+1];

        //initialize with maximum possible cuts (cut to single chars)
        for (int i=0; i<=len; i++) cut[i]=i-1;

        for (int i=0; i<len; i++){
            //odd length palindrome
            for (int j=0; i-j>=0 && i+j <len && s.charAt(i-j)==s.charAt(i+j); j++){
                cut[i+j+1] = Math.min(cut[i+j+1], 1+cut[i-j]);
            }
            //even length palindrome
            for (int j=1; i-j+1>=0 && i+j <len && s.charAt(i-j+1)==s.charAt(i+j); j++){
                cut[i+j+1] = Math.min(cut[i+j+1], 1+cut[i-j+1]);
            }
        }

        return cut[len];
    }
}

Reference

Leetcode