leetcode131 分割回文串

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

示例 1：

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

示例 2：

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

提示：

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

package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Parts {
    public List<List<String>> partition(String s) {
        Map<Integer, List<Integer>> allParts = getAllParts(s);
        // 组合
        List<Integer> parts = allParts.get(0);
        List<List<String>> res = new ArrayList<>();
        return appendNextParts(allParts, res, 0, s);
    }

    public List<List<String>> appendNextParts(Map<Integer, List<Integer>> allParts, List<List<String>> res, int start, String s) {
        if (start >= s.length()) {
            return new ArrayList<>();
        }
        if (!allParts.containsKey(start)) {
            return new ArrayList<>();
        }
        List<Integer> parts = allParts.get(start);
        List<List<String>> newParts = new ArrayList<>();
        for (int i = 0; i < parts.size(); i++) {
            String temp = s.substring(start, parts.get(i) + 1);
            List<List<String>> strings = appendNextParts(allParts, res, parts.get(i) + 1, s);
            if (!strings.isEmpty()) {
                for (List<String> string : strings) {
                    List<String> newString = new ArrayList<>();
                    newString.add(temp);
                    newString.addAll(string);
                    newParts.add(newString);
                }
            } else {
                List<String> newString = new ArrayList<>();
                newString.add(temp);
                newParts.add(newString);
            }
        }
        return newParts;
    }

    public Map<Integer, List<Integer>> getAllParts(String s) {
        Map<Integer, List<Integer>> res = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            List<Integer> singleParts = getSingleParts(i, s);
            res.put(i, singleParts);
        }
        return res;
    }

    public List<Integer> getSingleParts(int start, String s) {
        List<Integer> res = new ArrayList<>();
        // 所有
        for (int i = start; i < s.length(); i++) {
            if (isP(s, start, i)) {
                res.add(i);
            }
        }
        return res;
    }

    public boolean isP(String s, int start, int end) {
        if (start < 0 || end > s.length() - 1 || start > end) {
            return false;
        }
        if (start == end) {
            return true;
        }
        if (s.charAt(start) == s.charAt(end) && start == end - 1) {
            return true;
        }
        if (s.charAt(start) == s.charAt(end) && start == end - 2) {
            return true;
        }
        if (s.charAt(start) == s.charAt(end)) {
            return isP(s, start + 1, end -1);
        }
        return false;
    }

    public static void main(String[] args) {
        // aabbabbbaabbbbba
        // 1 找到所有回文串
        // 2 组合回文串
        String s = "aab";
        Parts parts = new Parts();
        System.out.println(parts.partition(s));
    }
}