Given a strings, cut_s_into some substrings such that every substring is a palindrome.

Return theminimumcuts needed for a palindrome partitioning ofs.

Have you met this question in a real interview?

Yes

Example

Given s ="aab",

Return1since 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
        if (s == null || s.length() == 0) {
            return 0;
        }

        int minCut = Integer.MAX_VALUE;
        int[] result = new int[s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            result[i] = i;
        }
        boolean[][] index = getIsPalindrome(s);

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (index[j][i - 1]) {
                    result[i] = Math.min(result[i], result[j] + 1);
                }
            }
        }
        return result[s.length()] - 1;


    }

    //identify all palindrome within the word
    private boolean[][] getIsPalindrome(String s) {
        boolean[][] result = null;
        if (s == null && s.length() == 0) {
            return result;
        }
        result = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            result[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            result[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }

        for (int length = 2; length < s.length(); length++) {
            for (int start = 0; start + length < s.length(); start++) {
                result[start][start + length] = result[start + 1][start + length - 1] && s.charAt(start) == s.charAt(start + length);
            }
        }
        return result;
    }
};

public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    //the last palindrome: the last palindrome part
    //to know the maximum number of cuts, we need to know the string before the last palindrome part how many cuts at least

    //sub problem
    //method 1
    //f[n] represents the the min number of palindrome on the first n char for palindrom partition
    //f[n] = min 0 <= j < n{f[j] + 1|S[j, n - 1]} is palindrome


    //method 2
    //f[n] represents the min number of cuts on the first n char for palindrome partition
    //f[n] = min 0 <= j < n{f[j] + 1|S[j, n - 1]} is palindrome


    public int minCut(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }


        char[] S = s.toCharArray();
        int n = S.length;
        int[] f = new int[n + 1];

        boolean[][] isPalin = isPalin(S);

        int i, j;
        f[0] = -1;
        for (i = 1; i <= n; i++) {
            f[i] = i - 1;
            for (j = 0; j < i; j++) {
                if (isPalin[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }

        return f[n];
    }

    private boolean[][] isPalin(char[] s) {
        int n = s.length;
        boolean[][] ans = new boolean[n][n];
        int i, j;
        for (i = 0; i < n; i++) {
            ans[i][i] = true;
            int start = i - 1;
            int end = i + 1;
            while (start >= 0 && end < n) {
                if (s[start] == s[end]) {
                    ans[start][end] = true;
                    start--;
                    end++;
                    continue;
                }

                break;
            }

            start = i - 1;
            end = i;
            while (start >= 0 && end < n) {
                if (s[start] == s[end]) {
                    ans[start][end] = true;
                    start--;
                    end++;
                    continue;
                }

                break;
            }
        }
        return ans;
    }
};