LeetCode_84_PalindromePartitioning

1. question: 分割回文串（中等）

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-partitioning

示例 1：

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

示例 2：

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

提示：

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

2. answers

这道题，表面上看是从大到小分割。但是本质上可以看成由小到大组合。可以看成组合问题，采用回溯法：

1. 第一个元素选择第一个字符，有s.length长度个选择
2. 第二个元素从第一个元素的后面开始选择
3. …以此类推
4. 注意，形成元素后，要判断是否是回文串，如果是，则继续下一个元素；如果不是，那继续寻找本元素；当遍历完整个数组也找不到时，则说明本元素的选择结束。
5. 判断回文串，可以采用首尾双指针法。

那么什么时候终止呢？当选择下一个元素的时候，如果起始下标超过了s.length，那么就说明切割完了。此时结束递归并返回。注意回溯。代码如下所示：

public class Solution_0083 {

    public List<List<String>> res = new ArrayList<>();
    public LinkedList<String> group = new LinkedList<>();

    public boolean isPalindrome(char[] chars, int start, int end) {

        while(start <= end) {
            if(chars[start++] != chars[end--]) return false;
        }

        return true;
    }

    public void recurPartition(char[] chars, int startIndex, int endIndex) {

        // 注意，递归终止条件
        if(endIndex == chars.length) {
            res.add(new ArrayList<>(group));
            return;
        }

        // 选择本元素
        // 判断是否是回文子串，如果是，则继续递归，直到遍历完整个字符串
        // 如果不是，则增大endIndex，直到找到，或者找不到，
        // 本元素有多种选择，[startIndex, endIndex]
        for (int i = endIndex; i < chars.length; i++) {

            // 判断是否是回文串，注意，结束位置，不同的选择是不一样的，因此结束位置是i，而不是固定的endIndex
            // 如果不是，则进行当前元素的下一个选择，
            if(!isPalindrome(chars, startIndex, i))
                continue;

            // 找到回文串，
            String s = String.valueOf(chars, startIndex, i - startIndex + 1);
            group.add(s);

            // 递归进行下一个选择，注意，下一个元素的选择要从本元素的结束位置的下一个开始，
            recurPartition(chars, i + 1, i + 1);

            // 回溯
            group.removeLast();
        }

    }

    public List<List<String>> partition(String s) {

        char[] chars = s.toCharArray();

        recurPartition(chars, 0, 0);
        return res;
    }

    public static void main(String[] args) {
        System.out.println();

//        String str = "aab";
        String str = "a";

        Solution_0083 s = new Solution_0083();

        List<List<String>> res = s.partition(str);

        for(List<String> list: res){

            for(String ss: list)
                System.out.print(ss + "\t");

            System.out.println();
        }
    }
}

为了方便，设置了两个下标，其实每次选择元素的时候，startIndex和endIndex初始值是一样的，因此可以去掉endIndex。

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。