Leetcode: 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:

We use dynamic programming twice, first we obtain the matrix that indicates if an element is palindrome (cf. Palindrome Partioning I). Then, we calculate the minCut till the element i, as follows:

•  If isPalindrome(0,i) then minCut[i]=0
• else minCut[i] = min( minCut[j]+1 && isPalindrome(i,j))

public class Solution {
    public int minCut(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        for(int length=0; length<s.length(); length++)
        {
            for(int start=0; start<s.length()-length; start++)
            {
                if(length==0)
                    isPalindrome[start][start] = true;
                else if(length==1)
                    isPalindrome[start][start+length] = s.charAt(start)==s.charAt(start+length);
                else
                    isPalindrome[start][start+length] = isPalindrome[start+1][start+length-1] && s.charAt(start)==s.charAt(start+length);
            }
        }
        
        int[] numberOfPalindromes = new int[s.length()];
        for(int i=0; i<s.length(); i++)
        {
            numberOfPalindromes[i] = isPalindrome[0][i] ? 0 : numberOfPalindromes[i-1]+1;
            for (int j=0; j<i; j++)
            {
                if(isPalindrome[j+1][i])
                    numberOfPalindromes[i] = Math.min(numberOfPalindromes[j]+1, numberOfPalindromes[i]);
            }
        }
        return numberOfPalindromes[s.length()-1];
    }
}