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.


public class Solution {
   
    public int minCut(String s) {
        int cuts[] = new int[s.length()];
        cuts[0] = 0;
        boolean cache[][] = new boolean[s.length()][s.length()];
        for (int i = 1; i < s.length(); i++) {
            cuts[i] = cuts[i-1]+1;
            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)
                        && (cache[j+1][i - 1] || j>=i-2)) {
                    cache[j][i] = true;
                    if(j==0) {
                        cuts[i] = 0;
                    } else {
                        cuts[i] = Math.min(cuts[i], cuts[j-1] + 1);
                    }
                }
            }
        }
        return cuts[s.length() - 1];
    }
}


============

public class Solution {
    public int minCut(String s) {
        if(s.length()==0)return 0;
        int[] c=new int[s.length()+1];
        for(int i=0;i<s.length();i++) {
            c[i]=Integer.MAX_VALUE;
        }
        c[s.length()]=-1;
        for(int i=s.length()-1;i>=0;i--){
            for(int a=i,b=i;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
            for(int a=i,b=i+1;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
        }
        return c[0];
    }
}