132. Palindrome Partitioning II

Description

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.

Solution

DP, time O(n ^ 2), space O(n ^ 2)

用DP就可以做，还需要使用一个额外的二维数组帮助判断substring是否回文，否则O(n ^ 3)的复杂度会TLE。

class Solution {
    public int minCut(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        
        int n = s.length();
        int[] minCut = new int[n + 1];  // minCut of s.substring(0, j)
        boolean[][] isPalin = new boolean[n][n]; // whether s.substring(i, j + 1) is palin
        minCut[0] = -1;
        
        for (int i = 1; i <= n; ++i) {
            minCut[i] = i - 1;  // cut between each character
            
            for (int j = i - 1; j >= 0; --j) {
                isPalin[j][i - 1] = s.charAt(j) == s.charAt(i - 1) 
                    && (i - j <= 3 || isPalin[j + 1][i - 2]); 
                if (isPalin[j][i - 1]) {
                    minCut[i] = Math.min(minCut[i], 1 + minCut[j]);
                }
            }
        }
        
        return minCut[n];
    }
}