leetcode132  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.

Subscribe to see which companies asked this question
           

<strong>本题是要求对一个字符串进行划分，使得每段都是回文串，求其中最少要“切”几刀。本题最简单的思路就是用DFS进行搜索，但会超时。</strong>
           

<strong>此题当然是可以用DP的思想来考虑，首先为了不重复判断，用isP[j][i]数组来记录从i到j的子串是否为回文，用cut数组记录最终的结果。</strong>
           

<strong>最重要的DP的递推式：cut[i] = Math.min(cut[i],cut[j-1]+1);  当j=0时，cut[i] = 0;</strong>
           

代码如下：
           

public class Solution {
    public int minCut(String s) {
        boolean[][] isP = new boolean[s.length()][s.length()];
        int[] cut = new int[s.length()];
        cut[0] = 0;
        isP[0][0] = true;
        for(int i = 1;i<s.length();i++){
            cut[i] = i;
            for(int j = 0;j<=i;j++){
                if((s.charAt(j)==s.charAt(i))&&((i-j)<=1||isP[j+1][i-1])){
                    isP[j][i] = true;
                }
                if(isP[j][i]){
                    if(j==0){
                        cut[i] = 0;
                    }else{
                        cut[i] = Math.min(cut[i],cut[j-1]+1);                        
                    }
                }
            }
        }
        return cut[s.length()-1];
    }
}