摘要：题目要求现在有一个字符串，将分割为多个子字符串从而保证每个子字符串都是回数。我们只需要找到所有可以构成回数的并且得出最小值即可。即将字符作为，将字符所在的下标列表作为。再采用上面所说的方法，利用中间结果得出最小分割次数。
题目要求
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.
现在有一个字符串s，将s分割为多个子字符串从而保证每个子字符串都是回数。问最少需要分割多少次。
思路一：HashMap缓存
这道题目的核心思想是动态编程，假设我们已经知道[0,1],[0,2]...[0,i-1]每个子字符串的最少分割数，那么我们可以得出[0,i]子字符串的最小分割数。我们只需要从第i个字符开始往回找所有可以和第i个字符构成回数,假设从第j个字符到第i个字符可以构成回数（0<=j<=i），那么以j作为分割线得到的最少分割数为cut[j-1]+1。我们只需要找到所有可以构成回数的j并且得出最小值即可。
刚开始，我选择利用hashmap记录所有可能构成回数的情况。即将字符作为key，将字符所在的下标列表作为value。这样每次遍历一个字符时，只需要从hashmap中找到该字符的所有下标并判断该子字符串是否是回数即可。
它有一个很明显的缺陷，就是当出现大量以单一字符构成的回数时，如aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaa会超时。很明显还有更好的存储中间结果的方式。
Map> cache = new HashMap>();
public int minCut(String s) {
if(s==null || s.length()==0) return 0;
int[] minCut = new int[s.length()+1];
minCut[0] = -1;
for(int i = 0 ; i list = new ArrayList();
list.add(i);
cache.put(cur, list);
}else{
int max = minCut[i] + 1;
List values = cache.get(cur);
for(int index : values){
if(isPalindrome(s.substring(index, i+1))){
max = Math.min(max, minCut[index]+1);
}
}
minCut[i+1] = max;
values.add(i);
}
}
return minCut[s.length()];
}
public boolean isPalindrome(String subString){
if(subString.length()<=1) return true;
char[] sArray = subString.toCharArray();
int left = 0,
right = subString.length()-1;
while(left
思路二：存储中间的回数结果
这里我们采用二维数组的方式来存储中间的回数结果。我们会新建一个boolean[s.length][s.length] isPalindrome,其中isPalindrome[i][j]代表从i开始j结束的子数组是否是回数。再采用上面所说的方法，利用中间结果得出最小分割次数。
public int minCut2(String s){
if(s==null || s.length()<=1) return 0;
int length = s.length();
boolean[][] isPalindrome = new boolean[length][length];
int[] result = new int[length];
char[] array = s.toCharArray();
for(int end = 0 ; end=0 ; start--){
if(array[start] == array[end]){
if(end-start<=2){
isPalindrome[start][end] = true;
}else{
isPalindrome[start][end] = isPalindrome[start+1][end-1];
}
}
if(isPalindrome[start][end]){
if(start==0){
result[end] = 0;
}else{
result[end] = Math.min(result[start-1]+1, result[end]);
}
}
}
}
return result[length-1];
}
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/68623.html
