题解 | #分割回文串-ii#

import java.util.*;
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int minCut (String s) {
        // write code here
        int len=s.length();
        if(len<1){
            return 0;
        }
        int [] minSub=new int [len+1];
        for(int i=1;i<=len;i++){
            minSub[i]=i-1;
        }
        for(int i=2;i<=len;i++){
            if(ispal(s,0,i-1)==true){
                minSub[i]=0;
            }
            for(int j=1;j<i;j++){
                if(ispal(s,j,i-1)==true){
                    minSub[i]=Math.min(minSub[i],minSub[j]+1);
                }
            }
        }
        return minSub[len];
    }
    public static boolean ispal(String str,int begin,int after){
        while(begin<after){
            if(str.charAt(begin)!=str.charAt(after)){
                return false;
            }
            begin++;
            after--;
        }
        return true;
    }
}