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.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        int n = s.length();
        int[] cuts = new int[n];
        boolean[][] isPalindrome = new boolean[n][n];
        char[] chars = s.toCharArray();
        
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = 0; j <= i; j++) {
                if (chars[i] == chars[j] && (j + 1 > i - 1 || isPalindrome[j + 1][i - 1])) {
                    isPalindrome[j][i] = true;
                    min = j == 0 ? 0 : Math.min(min, cuts[j - 1] + 1);
                }
            }
            cuts[i] = min;
        }
        return cuts[n - 1];
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] cuts = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            cuts[i] = i - 1;
        }
        // i as the moving center of a string
        for (int i = 0; i < n; i++) {
            // odd length
            // i as the center, left j + ith + right j 
            for (int j = 0; i - j >= 0 && i + j < n; j++) {
                if (chars[i - j] == chars[i + j ]) {
                    cuts[i + j + 1] = Math.min(cuts[i + j + 1], cuts[i - j] + 1);
                } else {
                    break;
                }
            }
            
            // even length, starting from ith and (i+1)th, then expand
            for (int j = 1; i - j + 1 >= 0 && i + j < n; j++) {
                if (chars[i - j + 1] == chars[i + j]) {
                    cuts[i + j + 1] = Math.min(cuts[i + j + 1], 1 + cuts[i - j + 1]);
                } else {
                    break;
                }
            }
        }
        return cuts[n];
    }
}