132 Palindrome Partitioning II

132. Palindrome Partitioning II

1. Question

Given a strings, partitionssuch that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning ofs.

For example, givens="aab", Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.

2. Implementation

(1) DP

思路:

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

        int n = s.length();
        // isPalindrome[i][j]指的是s[i...j]是否是palindrome
        boolean[][] isPalindrome = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }

        // 区间DP模型:
        // Outer for loop 枚举区间长度
        // Inner for loop 枚举区间的起点
        for (int len = 2; len <= n; len++) {
            for (int start = 0; start < n - len + 1; start++) {
                int end = start + len - 1;

                if (len == 2) {
                    if (s.charAt(start) == s.charAt(end)) {
                        isPalindrome[start][end] = true;
                    }
                }
                else {
                    if (s.charAt(start) == s.charAt(end) && isPalindrome[start + 1][end - 1]) {
                        isPalindrome[start][end] = true;
                    }
                }
            }
        }

        // cuts[i] 表示在s[0...i]中分割palindromes所需要的最小cuts
        int[] cuts = new int[n];

        for (int i = 0; i < n; i++) {
            if (isPalindrome[0][i]) {
                cuts[i] = 0;
            }
            else {
                // s[0...i]最多可以有i个cuts将s分割成palindrome
                cuts[i] = i;
                for (int j = 0; j < i; j++) {
                    // 注意这里判断s[j + 1...i]是否是palindrome，如果是的话, 那么s[0...i]所需要的最小cut就是
                    // s[0...i] 与 s[0...j] + 1(因为s[j + 1... i]是palindrome, 要在s[j]后cut一次得到这个palindrome， 所以加1)之间的
                    // 较小值
                    if (isPalindrome[j + 1][i]) {
                        cuts[i] = Math.min(cuts[i], cuts[j] + 1);
                    }
                }
            }
        }
        return cuts[n - 1];
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(n^2), 空间复杂度O(n^2)