Palindrome Partitioning II

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning ofs.

Have you met this question in a real interview? 

Yes

Example

For example, given s = "aab",

Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

public class Solution {

    /**

     * @param s a string

     * @return an integer

     */

    public int minCut(String s) {

        // write your code here

        int n = s.length();

        int[] cuting = new int[n];

        boolean[][] dp = new boolean[n][n];

        for(int i = 0; i < n; i++){

            

            cuting[i] = i;

            for(int j = 0; j <= i; j++){

                if(s.charAt(i) == s.charAt(j) && (i-j <= 1 || dp[i-1][j+1])){

                    dp[i][j] = true;

                    if(j > 0){

                        cuting[i] = Math.min(cuting[i], cuting[j-1] + 1);

                    } else{

                     cuting[i] = 0;

                    } 

                }

            }

        }

        return cuting[n-1];

    }

};