leetcode132 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

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

package leetcode;

import java.util.ArrayList;
import java.util.List;

public class Parts2 {
    public int minCut(String s) {
        int mid = s.length() / 2;
        if (isP(s, 0, s.length() - 1)) {
            return 0;
        }
        boolean p = isP(s, 0, mid);
        if (p) {
            return minCut2(reverse(s));
        } else {
            return minCut2(s);
        }
    }

    public int minCut2(String s) {
        int[] map = new int[s.length() + 1];

        int i = 0;
        List<Integer> cuts = new ArrayList<>();
        cuts.add(0);
        int[][] isPArr = new int[s.length() + 1][s.length() + 1];
        while (i < s.length() && cuts.size() > 0) {
            List<Integer> stepParts = new ArrayList<>();
            for (int cut : cuts) {
                if (map[cut] == 1) {
                    continue;
                }
                map[cut] = 1;

                for (int j = cut; j < s.length(); j++) {
                    if (isPArr[cut][j] == 1) {
                        stepParts.add(j);
                        continue;
                    }
                    if (isPArr[cut][j] == -1) {
                        continue;
                    }
                    if (isP(s, cut, j)) {
                        isPArr[cut][j] = 1;
                        stepParts.add(j);
                    } else {
                        isPArr[cut][j] = -1;
                    }
                }

//                List<Integer> parts = getSingleParts(cut, s);
//                stepParts.addAll(parts);
            }
            cuts.clear();

            for (int k = stepParts.size() - 1; k >= 0; k--) {
                int part = stepParts.get(k);
                if (map[part + 1] == 1) {
                    continue;
                }
                if (part + 1 >= s.length()) {
                    return i;
                }
                cuts.add(part + 1);
            }
            i++;
        }
        return i;
    }


    public String reverse(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }

    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 = "adabdcaebdcebdcacaaaadbbcadabcbeabaadcbcaaddebdbddcbdacdbbaedbdaaecabdceddccbdeeddccdaabbabbdedaaabcdadbdabeacbeadbaddcbaacdbabcccbaceedbcccedbeecbccaecadccbdbdccbcbaacccbddcccbaedbacdbcaccdcaadcbaebebcceabbdcdeaabdbabadeaaaaedbdbcebcbddebccacacddebecabccbbdcbecbaeedcdacdcbdbebbacddddaabaedabbaaabaddcdaadcccdeebcabacdadbaacdccbeceddeebbbdbaaaaabaeecccaebdeabddacbedededebdebabdbcbdcbadbeeceecdcdbbdcbdbeeebcdcabdeeacabdeaedebbcaacdadaecbccbededceceabdcabdeabbcdecdedadcaebaababeedcaacdbdacbccdbcece";
        // String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        // String s = "aabbabbbaabbbbba";
        // String s = "aabaabc";
        // String s = "aaabaa";
        Parts2 parts = new Parts2();
        System.out.println(parts.minCut(s));
    }
}