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 solution is a little bit hard to understand, but the key is use DP to keep track of previous minCut,

use an array to track whether s(i,j) is a palindrome

For this problem, firstly we consider the main part. It is a good way to look for the "state", and the "optimal solution" based on that state, to solve the DP problem. In other words, if you found the correct state, and the function of the state representing the optimal solution, all you need is some loops and initialization implementing the algorithm.

The algorithm below is from Yu's coding garden.

Here the state is not too hard ---- minimum cut. Define res[i] = the minimum cut from 0 to i in the string.

The result w =e need eventually is res[s.size()-1]. We know res[0]=0. Next we are looking for the optimal solution function f.

For example, let s = "leet".

f(0) = 0;  // minimum cut of str[0:0]="l", which is a palindrome, so not cut is needed.
f(1) = 1; // str[0:1]="le" How to get 1? 
                 f(1) might be:  (1)   f(0)+1=1, the minimum cut before plus the current char.
                                       (2)   0, if str[0:1] is a palindrome  (here "le" is not )
f(2) = 1; // str[0:2] = "lee" How to get 2?
                f(2) might be:   (1)  f(1) + 1=2
                                       (2)  0, if str[0:2] is a palindrome (here "lee" is not)
                                       (3)  f(0) + 1,  if str[1:2] is a palindrome, yes! 
f(3) = 2; // str[0:3] = "leet" How to get 2?
                f(3) might be:   (1)  f(2) + 1=2
                                       (2)  0, if str[0:3] is a palindrome (here "leet" is not)
                                       (3)  f(0) + 1,  if str[1:3] is a palindrome (here "eet" is not)
                                       (4)  f(1) + 1,  if str[2:e] is a palindrome (here "et" is not)
OK, output f(3) =2 as the result.

So, the optimal function is:

f(i) = min [  f(j)+1,  j=0..i-1   and str[j:i] is palindrome
                    0,   if str[0,i] is palindrome ]

public int minCut(String s) {
        int[] results = new int[s.length()];
        boolean[][] palindrome = new boolean[s.length()][s.length()];

        //pre-compute palindrome table for s(i,j)
        //only if (j-i)<2 (1 char) or palindrome[i+1][j-1] (abbd, the string between a and d, bb needs to be palindrome)
        for (int i=s.length()-1; i>=0; i--) {
            for (int j=i; j<s.length(); j++) {
                if (s.charAt(i)==s.charAt(j)&&(j-i<2||palindrome[i+1][j-1])) {
                    palindrome[i][j] = true;
                }
            }
        }

        for (int i=0; i<s.length(); i++) {
            int minCuts = s.length();
            //if string itself is a palindrome
            if (palindrome[0][i]) {
                results[i] = 0;
            //check each cut at the substring
            } else {
                for (int j=0; j<i; j++) {
                    //f(j)+1, if s(j+1) is a palindrome
                    if (palindrome[j+1][i]&&minCuts>results[j]+1) {
                        minCuts = results[j]+1;
                    }
                }
                results[i] = minCuts;
            }
        }

        return results[s.length()-1];
    }