[LintCode][要再做] #108 Palindrome Partitioning II

public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    public int minCut(String s) {
        // state: f[i] = min cuts needed for a palindrome partitioning of s.substring(0, i)
        // function: f[i] = Min(f[j] + 1, isPalindrome(s.substring(j, i)), for all j < i
        // initialize: f[0] = 0
        // result: f[s.length()]
        // write your code here
        
        //isPalindrome[i][j] = is s.substring(i, j + 1) a palindrome
        boolean [][] isPalindrome = getIsPalindrome(s);
        
        int f[] = new int[s.length() + 1];
        f[0] = -1;
        for (int i = 1; i <= s.length(); i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[s.length()];
    }
    
    private boolean[][] getIsPalindrome(String s) {
        boolean[][] p = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            p[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            p[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        for (int length = 2; length < s.length(); length++) {
            for (int i = 0; i + length < s.length(); i++) {
                p[i][i + length] = p[i + 1][i + length - 1] && s.charAt(i) == s.charAt(i + length);
            }
        }
        return p;
    }
    
};