Leetcode: Palindrome Partitioning 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.

Understand the problem:
The problem asks for partitioning a string s such that every substring of the partition is a palindrome. The mainly difference between the palindrome partition problem is it returns the minimum cuts needed for a palindrome partitioning of s. 

Naive Solution:
One naive solution is to find out a partition, then count the number of cuts. We maintain the minimum cuts. After we found all possible partitions, we return the minimal cuts. So the code looks very closed to the palindrome partitioning. 

Code (Java):

public class Solution {
    private int min = Integer.MAX_VALUE;
    
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        if (isPalin(s)) return 0;
        
        ArrayList<String> list = new ArrayList<String>();
        
        minCut(s, list);
        
        return min;
    }
    
    private void minCut(String s, ArrayList<String> list) {
        if (s.isEmpty()) {
            min = Math.min(min, list.size() - 1);
            return;
        }
        
        for (int i = 1; i <= s.length(); i++) {
            if (isPalin(s.substring(0, i))) {
                list.add(s.substring(0, i));
                minCut(s.substring(i), list);
                list.remove(list.size() - 1);
            }
        }
    }
    
    private boolean isPalin(String s) {
        if (s == null) return true;
        
        int start = 0;
        int end = s.length() - 1;
        
        while (start < end) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }
}

Discussion:
The naive solution has TLE error. Let's analyze the time complexity at first. Recursion takes O(n) time, however, note that the isPalindrome function also takes O(n) time as well. So the overall time complexity is O(n^2). 

A DP Solution:
Since we now know that most of the time takes on determining if a string is a palindrome. We can do it better to reduce the time. 
We define dp[ i ] means minimum cuts from i to end. 
We define palin[i][j] = true to indicate if string from index i to j is a palindrome. palin[i][j] is palindrome if and only if [i+1, j-1] is a palindrome AND s[i] = s[j]. Or j - i < 2 && s[i] == s[j], meaning the string s has at most 2 characters. 

Code (Java):

public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        
        int len = s.length();
        int[] dp = new int[len + 1];
        boolean[][] palin = new boolean[len][len];
        
        // initialize dp[]
        for (int i = 0; i < len; i++) {
            dp[i] = len - i;
        }
        
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if ((s.charAt(i) == s.charAt(j) && (j - i) < 2) || 
                    (s.charAt(i) == s.charAt(j) && palin[i + 1][j - 1])) {
                    palin[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0] - 1;
    }
}