Posted on 2013-04-15 13:52
小明 阅读(1481)
评论(0) 编辑 收藏 所属分类:
数据结构和算法
分析：
这个一个典型的可以用递归来解决问题，对于字符串s，先找出第一段回文字符串，然后递归的调用自己来切割余下的部分。
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;
}