Palindrome Partitioning II 108

Question

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example

Given s = "aab",

Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.

Solution

两次动态规划。第一次动态规划palindrome[i][j]，表示s中i~j的字符串是否是回文串。第二次动态规划根据palindrome求出cut[i]，即前i个字符最少要切几次才能将字符串切为回文串。

palindrome：

初始化：

palindrome[i][i]=true，palindrome[i][i+1] = (s.charAt(i) == s.charAt(i+1))

即初始化一个字符和两个字符的字符串。

状态函数：palindrome[i][j] = s.charAt(i) == s.charAt(j) && palindrome[i+1][j-1]，即两头字符要相等，同时中间字符串也要为回文串。

cut:

初始化：cut[i]=i-1，即前i个元素至多需要切i－1次,这里特别要注意cut[0]=-1，这是为了后面状态函数中j＝0时能够满足题意。

状态函数：cut[i]=min(cut[i], cut[j]+1)，即在i之前的位置上找一个切割点j，使得j~i的字符串为回文串（palindrome[j][i-1]=true），这样将前i个字符串切成回文串需要的次数为将前j个字符串切成回文串需要的最小次数＋1(1表示切j的这一次)，取不同j情况下的最小值即可。注意，i（前i个字符）和i－1（第i－1个字符）的含义和转换。

代码如下：

public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    private boolean[][] isPalindrome(String s){
        int m = s.length();
        boolean[][] result = new boolean[m][m];

        for(int i = 0; i < m; i++){
            result[i][i] = true;
        }

        for(int i = 0; i < m - 1; i++){
            result[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }

        for(int i = 2; i < m; i++){
            for(int j = 0; j < i - 1; j++){
                if(s.charAt(j) == s.charAt(i) && result[j + 1][i - 1]){
                    result[j][i] = true;
                }
            }
        }

        return result;
    }

    public int minCut(String s) {
        // write your code here
        if(s == null || s.length() == 0){
            return 0;
        }

        int n = s.length();
        int[] cut = new int[n + 1];
        boolean[][] palindrome = isPalindrome(s); 

        for(int i = 0; i <= n; i++){
            cut[i] = i - 1;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                if(palindrome[j][i - 1]){
                    cut[i] = Math.min(cut[i], cut[j] + 1);
                }
            }
        }

        return cut[n];
    }
};