一 题目：

二 思路：

回溯，不断尝试分割的可能，只有当前分割是回文串，才添加到回文串结果集里继续尝试

三 代码：

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;
    }
}