132 Palindrome Partitioning II

Given a strings, partition_s_such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning ofs.

Example:

Input:
 "aab"

Output:
 1

Explanation:
 The palindrome partitioning ["aa","b"] could be produced using 1 cut.

O(n ^ 2)

class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] sch = s.toCharArray();
        int len = s.length();
        boolean[][] isPalin = isPalin(sch);
        int[] dp = new int[len + 1];
        dp[0] = 0;
        for (int i = 1; i <= len; i++) {
            dp[i] = Integer.MAX_VALUE;
            for(int j = 0; j < i; j++) {
                if (isPalin[j][i - 1]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[len] - 1;
    }
    public boolean[][] isPalin(char[] s) {
        int len = s.length;
        boolean[][] arr = new boolean[len][len];
        int i, j, c;
        for(c = 0; c < len; c++) {
            i = j = c;
            while (i >=0 && j < len && s[i] == s[j]) {
                arr[i][j] = true;
                i--;
                j++;
            }
        }
         for(c = 0; c < len - 1; c++) {
            i = c;
            j = c + 1;
            while (i >=0 && j < len && s[i] == s[j]) {
                arr[i][j] = true;
                i--;
                j++;
            }
        }
        return arr;
    }
}