Palindrome Partitioning II, Leetcode 解题笔记

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.

DP问题,网上看到的最好的解释:
http://www.lifeincode.net/programming/leetcode-palindrome-partitioning-i-and-iijava/
In this problem, we often needs to check if the substring(i, j) of the original string is palindrome or not. So we need to save this very important information to an array to prevent checking a same substring for several times. This is a 2-D boolean array which is quite easy to generate. We can generate it from short length to long length. When s.charAt(i) is equal to s.charAt(j), if the array isPalindrome[i + 1][j – 1] is true, then we can update isPalindrome[i][j] = true.

In the previous problem, we can use recursive function to generate all possible string lists.

In this problem, if we use recursive solution, we will got TLE. So a DP solution is needed. We can use a 1-D array D[n] to save the minimum cut. For example, D[i] saves the number of minimum cut of substring(i, n). We can start from i = n – 1, and move i from right to left. When we want to get the D[i] for a new i, we can check every possible substrings from i to n, which means we can use another point j, in which j is between i and n. If substring(i, j) is a palindrome, then we can update D[i] = min(D[i], 1 + D[j + 1]).

This method can also be used in the first problem to save more time.

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++)
            isPalindrome[i][i] = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 2 || isPalindrome[i + 1][j - 1])
                        isPalindrome[i][j] = true;
                }
            }
        }
        int[] minCut = new int[n + 1];
        for (int i = n; i >= 0; i--)
            minCut[i] = n - 1 - i;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (isPalindrome[i][j]) {
                    minCut[i] = Math.min(minCut[i], 1 + minCut[j + 1]);
                }
            }
        }
        return minCut[0];
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s