Posted on 2013-04-15 13:52
小明 閱讀(1506)
評論(0) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
分析：
這個一個典型的可以用遞歸來解決問題，對于字符串s，先找出第一段回文字符串，然后遞歸的調(diào)用自己來切割余下的部分。
private boolean isPalindrome(String s){
int len = s.length();
if(len>1){
for(
int i=0;i<len/2;++i){
if(s.charAt(i)!=s.charAt(len-i-1)){
return false;
}
}
}
return true;
}
public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> result =
new ArrayList<ArrayList<String>>();
if(isPalindrome(s)){
ArrayList<String> as =
new ArrayList<String>();
as.add(s);
result.add(as);
}
int len= s.length();
for(
int i=1;i<len;++i){
String ss = s.substring(0,i);
//find the first part
if(isPalindrome(ss)){
ArrayList<ArrayList<String>> subResult = partition(s.substring(i));
//partition the remain part
for(ArrayList<String> as:subResult){
ArrayList<String> newas =
new ArrayList<String>();
newas.add(ss);
newas.addAll(as);
result.add(newas);
}
}
}
return result;
}