Palindrome Partitioning I, 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.

https://leetcode.com/problems/palindrome-partitioning-ii/

Analysis:

This problem is similar to Palindrome Partitioning. It can be efficiently solved by using dynamic programming. Unlike "Palindrome Partitioning", we need to maintain two cache arrays, one tracks the partition position and one tracks the number of minimum cut.

Solution:

public int minCut(String s) {
    int n = s.length();

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

    for (int j = 0; j < n; j++) {
        cut[j] = j; //set maximum # of cut
        for (int i = 0; i <= j; i++) {
            if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1])) {
                dp[i][j] = true;

                // if need to cut, add 1 to the previous cut[i-1]
                if (i > 0){
                    cut[j] = Math.min(cut[j], cut[i-1] + 1);
                }else{
                // if [0...j] is palindrome, no need to cut    
                    cut[j] = 0; 
                }    
            }
        }
    }

    return cut[n-1];
}

Solution II: TLE

public class Solution {
    public int minCut(String s) {
        if (s.length() == 0) {
            return 0;
        }    

        int n = s.length();
        int[][] res = new int[n][n];

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n-len; i++) {
                int j = i + len - 1;

                if (len == 2) {
                    res[i][j] = s.charAt(i) == s.charAt(j) ? 0 : 1;
                }

                else {

                if (s.charAt(i) == s.charAt(j) && res[i+1][j-1] == 0) {
                    res[i][j] = 0;

                } else {
                    res[i][j] = len;
                    for (int l = 1; l < len; l++) {
                        res[i][j] = Math.min(res[i][i+l-1] + res[i+l][j], res[i][j])+1;
                        if (res[i][j] == 0) {
                            break;
                        }
                    }
                }
                }
            }
        }

        return res[0][n-1];

    }
}