136. Palindrome Partitioning II

public class Solution {
    public int minCut(String s) {
        int len = s.length();
        int[] cut = new int[len+1];
        cut[len] = 0;
        boolean[][] table = createTable(s);
       
        for (int i=len-1; i>=0; i--) {
            cut[i] = len-i;
            for (int j=i; j<len; j++) {
                if (table[i][j]) cut[i] = Math.min(cut[i], cut[j+1]+1);
            }
        }
       
        return cut[0]-1;
    }
   
    public boolean[][] createTable(String s) {
        boolean[][] table = new boolean[s.length()][s.length()];
        for (int i=0; i<s.length(); i++) {
            table[i][i] = true;
        }
       
        for (int i=0; i<s.length(); i++) {
            int l = i-1;
            int r = i;
            while (l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)) {
                table[l--][r++] = true;
            }
           
            l = i-1;
            r = i+1;
            while (l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)) {
                table[l--][r++] = true;
            }
        }
       
        return table;
    }
}