摘要：題目要求現(xiàn)在有一個(gè)字符串，將分割為多個(gè)子字符串從而保證每個(gè)子字符串都是回?cái)?shù)。我們只需要找到所有可以構(gòu)成回?cái)?shù)的并且得出最小值即可。即將字符作為，將字符所在的下標(biāo)列表作為。再采用上面所說的方法，利用中間結(jié)果得出最小分割次數(shù)。
題目要求
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.
現(xiàn)在有一個(gè)字符串s，將s分割為多個(gè)子字符串從而保證每個(gè)子字符串都是回?cái)?shù)。問最少需要分割多少次。
思路一：HashMap緩存
這道題目的核心思想是動(dòng)態(tài)編程，假設(shè)我們已經(jīng)知道[0,1],[0,2]...[0,i-1]每個(gè)子字符串的最少分割數(shù)，那么我們可以得出[0,i]子字符串的最小分割數(shù)。我們只需要從第i個(gè)字符開始往回找所有可以和第i個(gè)字符構(gòu)成回?cái)?shù),假設(shè)從第j個(gè)字符到第i個(gè)字符可以構(gòu)成回?cái)?shù)（0<=j<=i），那么以j作為分割線得到的最少分割數(shù)為cut[j-1]+1。我們只需要找到所有可以構(gòu)成回?cái)?shù)的j并且得出最小值即可。
剛開始，我選擇利用hashmap記錄所有可能構(gòu)成回?cái)?shù)的情況。即將字符作為key，將字符所在的下標(biāo)列表作為value。這樣每次遍歷一個(gè)字符時(shí)，只需要從hashmap中找到該字符的所有下標(biāo)并判斷該子字符串是否是回?cái)?shù)即可。
它有一個(gè)很明顯的缺陷，就是當(dāng)出現(xiàn)大量以單一字符構(gòu)成的回?cái)?shù)時(shí)，如aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaa會(huì)超時(shí)。很明顯還有更好的存儲(chǔ)中間結(jié)果的方式。
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
思路二：存儲(chǔ)中間的回?cái)?shù)結(jié)果
這里我們采用二維數(shù)組的方式來存儲(chǔ)中間的回?cái)?shù)結(jié)果。我們會(huì)新建一個(gè)boolean[s.length][s.length] isPalindrome,其中isPalindrome[i][j]代表從i開始j結(jié)束的子數(shù)組是否是回?cái)?shù)。再采用上面所說的方法，利用中間結(jié)果得出最小分割次數(shù)。
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];
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/68623.html
