题解 | #所有的回文子串I# Java

这个函数使用回溯法来搜索所有可能的分组方案。它首先定义一个名为 res 的列表来存储最终结果，然后调用 backtrack 函数来进行搜索。backtrack 函数接受四个参数：res、tempList、s 和 start。其中，res 是最终结果列表，tempList 是当前的分组方案，s 是输入字符串，而 start 是当前搜索的起始位置。

在 backtrack 函数中，我们首先检查是否已经搜索到字符串的末尾。如果是，则将当前的分组方案添加到最终结果列表中。否则，我们从 start 开始遍历字符串，对于每个位置 i，如果从 start 到 i 的子串是一个回文串，则将其添加到当前分组方案中，并继续搜索下一个位置。当搜索完成后，我们需要将当前分组方案中最后添加的元素删除，以便进行下一轮搜索。

public class Solution {

    public String[][] partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(res, new ArrayList<>(), s, 0);

        // 对答案的处理
        String[][] result = new String[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i).toArray(new String[0]);
        }
        return result;
    }

    private void backtrack(List<List<String>> res, List<String> tempList, String s,
                           int start) {
        if (start == s.length()) { // 终止条件
            res.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < s.length(); i++) {
                if (isPalindrome(s, start, i)) {
                    tempList.add(s.substring(start, i + 1)); // 处理
                    backtrack(res, tempList, s, i + 1); // 回溯
                    tempList.remove(tempList.size() - 1);// 撤销处理
                }
            }
        }
    }

    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) return false;
        }
        return true;
    }
}

希望以后回溯别这么懵逼了