题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

回文串是正着读和反着读都一样的字符串。

思考

1、这题其实难点挺多的
2、你怎么去切割，怎么判断回文串（怎么定位下标位置）
3、对回溯中for循环中的局部变量进行判断

代码和注释

/**
    回溯算法：
    1、递归参数
    2、结束条件
    3、每层递归
 */
class Solution {
    // 结果集
    List<List<String>> res = new ArrayList<>();
    // 路径结果集
    LinkedList<String> path = new LinkedList<>();


    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return res;
    }


    public void backtracking(String s, int startIdx){
        if(startIdx == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        // 广度
        for(int i = startIdx; i < s.length(); i++){
            // 判断回文字符串
            if(isPalindrome(s, startIdx, i)){
                // 难点：（因为每轮递归的时候，他都会向上一层去走，【那下一次一定会在之前递归时i的基础上+1，那就顺利向后判断了】）
               String str = s.substring(startIdx, i+1);
               path.add(str);
            }else{
                continue;
            }
            // 开始递归，进入跟深的子树
            backtracking(s, i + 1);
            path.removeLast();
        }
    }

    //判断是否是回文串(双指针)
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

}