[leetcode] Palindrome Partitioning II

http://leetcode.com/onlinejudge#question_132

Question:

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.

Solution:

DP problem, but my first try failed due to time limitation. The root cause is you should try to optimize the Palindrome calculation. The solution below borrows from others idea found from the discussion page. Thanks to the author.

public class Solution {
    public int minCut(String s) {
        int leng = s.length();
        if(leng == 0 || leng == 1) return 0;
        boolean[][] isPal = new boolean[leng][leng];

        int[] dp = new int[leng]; 
        for (int i = 0; i < leng; i++) {
            dp[i] = leng - 1 - i;
        }

        for (int i = leng - 1; i >= 0; --i) {
            for (int j = i; j < leng; ++j) {
                if (s.charAt(i) == s.charAt(j) && (j <= i + 2 || (i + 1 < leng && j - 1 >= 0 && isPal[i + 1][j - 1]))) {
                    isPal[i][j] = true;
                    if(j+1 < leng){
                        dp[i] = Math.min(dp[i], 1 + dp[j + 1]);
                    }else {
                        dp[i] = 0;
                    }
                }
            }
        }

        return dp[0];
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Solution s = new Solution();
        int cut = s.minCut("abccdcba");
        System.out.println(cut);
    }

}