[LeedCode] 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.

[Solution].java

public class Solution {
    public int minCut(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s == null || s.length() < 1) return 0;

        int[] dp = new int[s.length()];
        dp[0] = 0;
        boolean[][] palindromes = new boolean[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) palindromes[i][i] = true;

        for(int i = 1; i < s.length(); i++){
          dp[i] = count(s, i, dp, palindromes);
        }
        return dp[s.length() - 1];
    }

    public int count(String s, int pos, int[] dp, boolean[][]palindromes){
    	int min = dp[pos - 1] + 1;
    	for(int i = pos - 1; i > 0; i--){
    		if(isPalindrome(s, i, pos, palindromes) && (dp[i - 1] + 1) < min){
    			min = dp[i - 1] + 1;
    		}
    	}
    	if(isPalindrome(s, 0, pos, palindromes)) min = 0;
    	return min;
    }

    public boolean isPalindrome(String s, int begin, int end, boolean[][] palindromes){
    	if(s.charAt(begin) == s.charAt(end)){
    		if(begin == end - 1) palindromes[begin][end] = true;
    		else palindromes[begin][end] = palindromes[begin + 1][end - 1];
    	}
        return palindromes[begin][end];
    }
}