面试指南——回文最小分割数

题目:

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

举例:

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

str=”ACDCDCDAD”,最少需要切两次,比如”A”,”CDCDC”,”DAD”,所以返回2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * 左成云代码分析:
 * 鲁棒性,初始化一个长宽为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开始。
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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<str.length();i++){  
            dp[i] = min;  
            for(int j=0;j<=i;j++){  
                if(str.charAt(j) == str.charAt(i) && ( i-j <= 2 || map[j+1][i-1])){  
                    map[j][i] = true;  
                    dp[i] = j==0 ? 0 :Math.min(dp[i], dp[j-1] + 1);  
                }  
            }  
        }  
         
        return dp[str.length()-1];  
    }
        //通过遍历判断回文串
    public static int minCut(String s) {  
        if(s == null||s.length() == 0)  
            return 0;  
        int[] dp=new int[s.length()];  
        //dp[i]存放(0,i)即以i的字符结束的子串的最小切割数,则所求为dp[s.length()-1];  
        dp[0]=0;//一个字符,不需要切割  
        for(int i=1;i<s.length();i++)  
            {  
            //dp[i]赋初值  
            dp[i]=is_palindrome(s.substring(0,i+1))?0:i+1;
            //System.out.println(Arrays.toString(dp));
            //  1=<j<=i的子串回文判定  
            for(int j=i;j>=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<end)  
            {  
            if(s.charAt(begin)!=s.charAt(end))  
                return false;  
            begin++;  
            end--;              
        }  
        return true;  
    }  
   
 // for test
    public static String getRandomStringOnlyAToD(int len) {
        int range = 'D' - 'A' + 1;
        char[] charArr = new char[(int) (Math.random() * (len + 1))];
        for (int i = 0; i != charArr.length; i++) {
            charArr[i] = (char) ((int) (Math.random() * range) + 'A');
        }
        return String.valueOf(charArr);
    }

    public static void main(String[] args) {
        int maxLen = 10;
        int testTimes = 5;
        String str = null;
        for (int i = 0; i != testTimes; i++) {
            str = getRandomStringOnlyAToD(maxLen);
            System.out.println(""" + str + """ + " : ");
            System.out.println("--"+minCut(str));
            System.out.println("++"+getTheLeastSplit(str));
        }
    }

}
0 条评论
发表一条评论