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];
    }
}

(2) DP With One Pass

思路: 上一个解法用了两次 run了两个for loop, 事实上我们可以同时更新isPalindrome的数组和dp数组。如果s[start...end]是一个palindrome的话，那么这个区间是不需要任何切割的, dp[end]的最小切割数等于min(dp[end], dp[start - 1] + 1). 当star = 0时，说明dp[0...end]都是palindrome，这时候dp[end] = 0。

class Solution {
    public int minCut(String s) {
        int n = s.length();

        int[] dp = new int[n + 1];

        boolean[][] isPalindrome = new boolean[n][n];

        for (int end = 0; end < n; end++) {
            dp[end] = end;
            for (int start = 0; start <= end; start++) {
                if (s.charAt(start) == s.charAt(end) && (end - start <= 1 || isPalindrome[start + 1][end - 1])) {
                    isPalindrome[start][end] = true;
                    dp[end] = start == 0 ? 0 : Math.min(dp[end], dp[start - 1] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

(3) DP with Time Optimization

思路: 我们可以将时间复杂度进一步降低，做法则是以字符串s的任意一点i中心，分别向两边扩展，找出相应的palindrome并且同时更新dp数组

class Solution {
    public int minCut(String s) {
        int n = s.length();

        int[] dp = new int[n];

        // Initialize dp[i] with maximum cuts at i
        for (int i = 0; i < n; i++) {
            dp[i] = i;
        }

        for (int i = 0; i < n; i++) {
            // Find Palindrome with odd length centered at i
            getMinCuts(dp, s, i, i);
            // Find Palindrome with even length centered at i and i + 1
            getMinCuts(dp, s, i, i + 1);
        }
        return dp[n - 1];
    }

    public void getMinCuts(int[] dp, String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            if (start == 0) {
                dp[end] = 0;
            }
            else {
                dp[end] = Math.min(dp[end], dp[start - 1] + 1);
            }
            --start;
            ++end;
        }
    }
}

3. Time & Space Complexity

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

DP with Time Optimization：时间复杂度O(n), 空间复杂度O(n)