一 题目：
二 思路：
回溯，不断尝试分割的可能，只有当前分割是回文串，才添加到回文串结果集里继续尝试
三 代码：
public class 分割回文串131 {
//存储返回结果
List<List<String>> res = new LinkedList<>();
//存储已经是回文的分割结果
Deque<String> deque = new LinkedList<>();
public List<List<String>> partition(String s) {
if (s==null || s.length()<1){
return res;
}
// 结果集，元数据，第0个数据判断要不要拼到上一个字符串上还是独立，当前已集成结果
search(s,0);
return res;
}
//从startIndex是上一层的分割线，这次寻找新的分割
private void search( String s, int startIndex) {
//如果全部都分割判断结束了，说明deque存储的都是回文字符串了，直接添加
if(startIndex>=s.length()){
res.add(new LinkedList<>(deque));
return;
}
//每个地方都尝试分割一次
for (int i = startIndex; i <s.length() ; i++) {
//如果这种分割得到的本次字符串是回文,就记录，并继续向下尝试分割
if (isPartition(s,startIndex,i)){
String str = s.substring(startIndex, i + 1);
deque.addLast(str);
search(s,i+1);
deque.removeLast();
}else {
continue;
}
}
}
/**
* 是否是回文串
*/
boolean isPartition(String s,int start ,int end){
while (start<end){
if (s.charAt(start)!=s.charAt(end)){
return false;
}else {
start++;
end--;
}
}
return true;
}
}
