132. 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.

解法1： DP O(n^2) Time + O(n^2) Space

用一个二维数组pal[i][j]表示，子字符串s[i,j]是否为一个palindrome。
同时用一个dp数组dp[i]表示的是[0, i]的字符串的最小cut
那么我们可以不停的尝试每一个子字符串[j, i]，如果[j,i]为palindrom，那么他的最小cut
就是dp[j - 1] + 1, 不停的变换j就可以求的对应的dp[i]的最小值。

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
class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        int[] dp = new int[n];  // dp[i] is the min cut for str [0, i]
        for (int i = 0; i < n; i++) {
            dp[i] = i;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j) && (i - j + 1 <= 2 || pal[j + 1][i - 1])) {
                    pal[j][i] = true;
                    dp[i] = Math.min(dp[i], j == 0 ? 0 : dp[j - 1] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}