回溯算法05-分割回文子串(Java)

5.分割回文子串

题目描述

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

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

示例 1：

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

示例 2：

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

题目分析

本题是回溯算法解决字符串分割问题，通过下面示例我们不难看出分割的方法：

1.partition(String s) 方法是入口点。它初始化了一个空的路径列表 path 和一个结果列表 result，然后调用 backtrack(String s) 方法来进行递归回溯。

2.backtrack(String s) 方法是递归的关键部分。它首先检查传入的字符串是否为空，如果是，则将当前路径添加到结果列表中，并返回。这是递归的终止条件。

3.接下来，使用一个 for 循环来遍历字符串 s 的所有可能的切割点（即 i 的位置）。在每个位置，它将字符串分成两部分：before（i 之前的部分）和 after（i 之后的部分）。

4.在每个切割点，它检查 before 部分是否为回文子串。如果是，就将 before 添加到路径列表中，并继续递归调用 backtrack(after) 方法来处理 after 部分。

5.递归调用结束后，需要将当前添加的 before 部分从路径列表中移除，以便尝试其他可能的组合。

6.isPalindrome(String substring) 方法用于检查传入的字符串是否为回文子串。它使用双指针法来进行检查，如果首尾字符相同，则向中间移动指针，直到两个指针相遇或交叉，否则返回 false。

Java代码实现

LinkedList<String> path = new LinkedList<>();
    List<List<String>> result = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backtrace(s);
        return result;
    }

    private void backtrace(String s) {
        if (s.equals("")) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            String subBefore = s.substring(0, i + 1);
            String subAfter = s.substring(i + 1);
            if (isBack(subBefore)) {
                path.add(subBefore);
                backtrace(subAfter);
                path.removeLast();
            }
        }
    }

    private boolean isBack(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left <= right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }