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.

求最佳解的问题通常用DP,这道题用到两个DP的矩阵。首先一个一维矩阵MinCut[i]来存s[0:i]的minCut,那怎么样从MinCut[i-1]得到MinCut[i]呢?用j =0 : i-1, 如果s[j+1:i]是palindrome的话,MinCut[i] = MinCut[j] + 1;抄一个例子
For example, let s = “leet”.
f(0) = 0; // minimum cut of str[0:0]=”l”, which is a palindrome, so not cut is needed.
f(1) = 1; // str[0:1]=”le” How to get 1?
f(1) might be: (1) f(0)+1=1, the minimum cut before plus the current char.
(2) 0, if str[0:1] is a palindrome (here “le” is not )
f(2) = 1; // str[0:2] = “lee” How to get 2?
f(2) might be: (1) f(1) + 1=2
(2) 0, if str[0:2] is a palindrome (here “lee” is not)
(3) f(0) + 1, if str[1:2] is a palindrome, yes!
f(3) = 2; // str[0:3] = “leet” How to get 2?
f(3) might be: (1) f(2) + 1=2
(2) 0, if str[0:3] is a palindrome (here “leet” is not)
(3) f(0) + 1, if str[1:3] is a palindrome (here “eet” is not)
(4) f(1) + 1, if str[2:e] is a palindrome (here “et” is not)
OK, output f(3) =2 as the result.

有了以上的这个minCut以外,还是不能通过大的case,因为判断palindrome太慢了,我们同样用DP的方法,利用一个二维矩阵isPal. isPal[i][j] = true表示s[i:j]是palindrome,怎样生成这个矩阵呢?首先单独的一个字符肯定是palindrome,然后如果charAt[i] == charAt[j] && isPal[i+1][j-1] == true,那么isPal[i][j]就应该是true了。注意因为我们要用isPal[i+1][j-1],所以i是从s.length向0扫描,而j是从i向s.length()扫描. 注意代码中分了i == j, j-i == 1 和j -i > 1的三种情况。

public class Solution {
    public int minCut(String s) {
        boolean [][] isPal = new boolean[s.length()][s.length()]; //(if s(i-j) is palindrome
        //calculate the isPal matrix
        for(int i = s.length()-1; i >= 0; i--)
        {
            for(int j = i; j < s.length(); j++)
            {
                if (j == i) // one char
                    isPal[i][j] = true;
                else if ((j - i == 1) && s.charAt(i) == s.charAt(j))// twp char next to each other
                    isPal[i][j] = true;
                else if ((s.charAt(i) == s.charAt(j) && isPal[i+1][j-1])) // other 
                    isPal[i][j] = true;
            }
        }
        //calculate minCut array
        int [] minCut = new int[s.length()]; // stores (0:i) minCut 
        minCut[0] = 0; // no cut needed for 1 char
        for(int i = 1; i < s.length(); i++)
        {
            if(isPal[0][i]) // if the whole string is pal, no need to check
            {
                minCut[i] = 0;
                continue;
            }
            minCut[i] = minCut[i-1] + 1; // minCut is at least minCut[i-1]+1, 
            for(int j = 0; j < i ; j++) //test j = (0:i) see if isPal[j][i] is true
            {
                if (isPal[j+1][i])
                {
                    minCut[i] = Math.min(minCut[i], minCut[j] + 1);
                }
            }
        }
        return minCut[s.length()-1];
    }
}

Second Submission:
A few things to pay attention.
First when creating the isPal, 3 conditions, i=j, i=j+1 and other.
Then when generating the minCut, check if j+1 i is palindrome and make minCut[i] = Math.min(MinCut[i], minCut[j]+1) if true.

public class Solution {
    public int minCut(String s) {
        boolean [][] isPal = new boolean [s.length()][s.length()];
        for(int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (i == j)
                    isPal[i][j] = true; // single char must be pal
                else if (j == i+1) // if two cascading char
                    isPal[i][j] = s.charAt(i) == s.charAt(j);
                else 
                    isPal[i][j] = (s.charAt(i) == s.charAt(j) && isPal[i+1][j-1]);
            } 
        }
        int [] minCut = new int [s.length()];
        minCut[0] = 0; // one char only 1 cut
        for( int i = 1; i < s.length(); i++) {
            if (isPal[0][i])
                minCut[i] = 0;
            else {
                minCut[i] = minCut[i-1] + 1; // init minCut to largest possible 
                for(int j = 0; j < i; j++) {
                    if (isPal[j+1][i]) {
                        minCut[i] = Math.min(minCut[i], minCut[j] + 1);
                    }
                }
            }
        }
        return minCut[s.length() - 1];
    }
}

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