题目:

给定一个字符串str,返回把str全部切成回文子串的最小分割数。

举例:

str="ABA" ,不需要切割,返回0;

str="ACDCDCDAD",最少需要切两次,比如"A","CDCDC","DAD",所以返回2.
/* * 左成云代码分析: * 鲁棒性,初始化一个长宽为str.length()的二维数组,初始化min=Integer的最小值,初始化长度str.length的dp数组 * dp[0]=0,如果只有一个字符,不需要分割,如果字符串长度大于1,判断第一个字符和第二个字符是否相等,如果相等,dp[1]=0,否则dp[1]=1; * 从i=2开始遍历,每次初始化dp[i]=min;将原来的每次遍历判断回文串优化为通过map数组判断回文串。其余思想一样。 */ /* * 鲁棒性,初始化dp数组,长度为字符串的长度 * dp[i]存放(0,i)即以i的字符结束的子串的最小切割数,则所求为dp[s.length()-1]; * 当只有一个字符时,不需要切割,dp[0]=0 * 从i=1开始遍历,当s.substring(0,i+1)是回文时,dp[i]=0,不需要分隔,否则,dp[i]=i,表示至多分割i次 * 对于任意大于1的i,如果s.substring(j,i+1),是回文时,dp[i]=min(dp[i],dp[j-1]+1); * 这句话的意思是,如果s.substring(j,i+1)回文,我们只需要把j之前的字符串切割开来,也就是分割次数为dp[j-1]+1; * s.substring(begin,end),包含begin,不包含end,计数从0开始。 */
public class 回文最少分割数 { //左成云代码 public static int getTheLeastSplit(String str){ if(str == null || str.length() == 0) return 0; boolean [][] map = new boolean [str.length()][str.length()]; int min = Integer.MAX_VALUE; int [] dp = new int[str.length()]; dp[0] = 0; if(str.length() >= 2) dp[1] = str.charAt(0) == str.charAt(1) ? 0: 1; for(int i=2;i=1;j--) { if(is_palindrome(s.substring(j,i+1))) { dp[i]=Math.min(dp[i],dp[j-1]+1); } } //System.out.println(i); } return dp[s.length()-1]; } //判断回文串例程 public static boolean is_palindrome(String s) { int begin=0; int end=s.length()-1; while(begin