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.

public int minCut(String s) {
        int n = s.length();
        int[] cut = new int[n+1];
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            // check odd length palindrome
            for (int j = 0; i-j >=0 && i+j < n && s.charAt(i-j) == s.charAt(i+j); j++) {
                cut[i+j+1] = Math.min(cut[i+j+1], 1+cut[i-j]);
            }
            
            // check even length palindrome
            for (int j = 0; i-j >= 0 && i+j+1 < n && s.charAt(i-j) == s.charAt(i+j+1); j++) {
                cut[i+j+2] = Math.min(cut[i+j+2], 1+cut[i-j]);
            }
        }
        
        return cut[n];
    }

DP题目有时候思路很简单很对称。这道题的基本思路如下:
假设 a b a c
用一个数组表示截止到每个字母(字母前)有几个cut
初始值为:
str = [a b a c]
cut = [0 1 2 3]

以第i个字母为中心,check它左右对称位置的字母是否相等,如果相等,则组成了palindrome,那么cut就应该相应的减少。

例如在b的位置, i = 1, str[i-1] == str[i+1], 所以在i+1这个位置的后面,即cut[i+2],cut数变成min(cut[i+2], cut[i-1] + 1)
[a, b, a, c]
[0, 1, 2, 1]

以上palindrome是odd length,再举一个even length的例子
str = [b, a, a, b, c]
cut = [0, 1, 2, 3, 4]
例如在i = 1的位置 str[i-0] == str[i+0+1], str[i-1] == str[i+1+1], 所以在cut[i+3]的位置上,变成min(cut[i+3], cut[i-1] + 1)

总结以上两个例子,
odd length: i-j >= 0 && i+j = 0 && i+j+1 < cut.length && str[i-j] == str[i+j+1]情况下,
cut[i+j+2] = min(cut[i+j+2], 1+cut[i-j])。需要保证i+j+2在cut长度范围内。

注意,如果整个str就是一个palindrome,例如
str = [b, b]
对于i = 0, 只check j = 0的时候,因为需要保证i+j+1在cut长度范围内,这样就找不到palindrome了。所以cut长度选为n+1而不是n,n是str的长度。

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