131. 分割回文串 - 力扣（LeetCode）

一、题目

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

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：​​​​​​​

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

二、代码

class Solution {
    public List<List<String>> partition(String s) {
        // 双层List，用来记录所有的分割方案
        List<List<String>> ans = new ArrayList<>();
        // 如果字符串只有一个字符，直接将其加入到答案中
        if (s == null || s.length() < 2) {
            List<String> cur = new ArrayList<>();
            cur.add(s);
            ans.add(cur);
        } else {
            char[] str = s.toCharArray();
            int N = str.length;
            // check[i][j]：i~j范围的字符串是回文串就为true，不是回文串就是false
            boolean[][] checkMap = createCheckMap(str, N);
           
            // 递归回溯，找到所有的分割情况
            process(s, 0, 1, checkMap, new ArrayList<>(), ans);
        }
        return ans;
    }

    // 构造回文串检查预处理结构
    public static boolean[][] createCheckMap(char[] str, int n) {
        // check[i][j]：i~j范围的字符串是回文串就为true，不是回文串就是false
        boolean[][] check = new boolean[n][n];
        // 先给对角线赋值赋值，只有一个字符肯定都是回文串
        for (int i = 0; i < n; i++) {
            check[i][i] = true;
        }
        // 再给第二条对角线赋值，两个字符，如果两个字符相等，那么就是回文串，如果两个字符不等，就不是回文串
        for (int i = 0; i < n - 1; i++) {
            check[i][i + 1] = str[i] == str[i + 1];
        }

        // 没有i > j的情况，dp数组左下半部分无效
        // 给普遍位置赋值
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                // 当str[i] == str[j]，并且i+1~j-1范围还是一个回文串，就说明i~j范围是一个回文串
                check[i][j] = str[i] == str[j] && check[i + 1][j - 1];
            }
        }

        return check;
    }

    // s[0....i-1]的划分方案都存到path里去了
    // 此时对s[i..j-1]进行考察，看s[i...j - 1]是否为一个回文串，如果是的话，就将i~j-1部分分割出来加入到path，然后再去尝试考察s[j...]如何切分
    public static void process(String s, int i, int j, boolean[][] checkMap, List<String> path, List<List<String>> ans) {
        // s[i...N-1]   已经递归到结尾了
        if (j == s.length()) {
            // 此时0~i-1的划分方案都已经放入到path了，如果此时i~j-1是一个回文串，并且j遍历完了整个字符串，就说明我们将i~j-1切分出来，加入到ans中，此时ans中就收集好了一种切分方案
            if (checkMap[i][j - 1] ) {
                // 将i~j-1切分出来加入的path中
                path.add(s.substring(i, j));
                // 将path加入到ans，至此ans收集到了一种切分方案
                ans.add(copyStringList(path));
                // 恢复现场，需要将path中的最后一个切分删掉，留给其他的尝试
                path.remove(path.size() - 1);
            }
        // s[i...j-1]   还没有递归到结尾
        } else {
            // 判断能否回溯的条件，如果此时i~j-1是回文串，所以i~j-1是可以切分出来的，加入到path中
            if (checkMap[i][j - 1]) {
                // 将i~j-1切分出来加入到path中
                path.add(s.substring(i, j));
                // 此时0~j-1都已经找到切分方案加入到path了
                // 下面我们需要去尝试在j~N-1范围内找到一个可以向下走的分支
                // 从判断j~j+1范围开始，看j~j+1是否为一个回文串可以且分出来
                process(s, j, j + 1, checkMap, path, ans);
                // 恢复现场
                path.remove(path.size() - 1);
            }
            // 执行到这里，0~i-1的切分方法都已经加入到path了，并且切分i~j-1的方案也已经尝试了（i~j-1有可能可以切分，也有可能无法切分，取决于checkMap[i][j - 1]）
            // 下面我们继续向下递归，到下一个划分点i和j+1，去判断i~j+1范围的字符串是否为回文串，看能不能将这一部分且分出来。
            // 这里不用去考虑是不是要在某些时候将i增加来尝试所有的可能性，因为将i加1进行尝试的前提是i前面已经找到了切分方法，而这个已经囊括在了上面代码的process(s, j, j + 1, checkMap, path, ans)中
            process(s, i, j + 1, checkMap,  path, ans);
        }
    }

    // 将结果复制到新的List中返回
    public static List<String> copyStringList(List<String> list) {
        List<String> ans = new ArrayList<>();
        for (String str : list) {
            ans.add(str);
        }
        return ans;
    }
}

三、解题思路 

这道题就是写一个暴力尝试，将所有可能的尝试方法都尝试一遍收集答案。