LeetCode——分割回文串

Q：给定一个字符串s，分割s使得s的每一个子串都是回文串
返回所有的回文分割结果。（注意：返回结果的顺序需要和输入字符串中的字母顺序一致。）
例如:给定字符串s="aab",
返回
[↵ ["aa","b"],↵ ["a","a","b"]↵ ]
A：这道题使用回溯的方法
注意：

• list加入array时要用拷贝，不要直接加入，否则之后list变化会导致array中的list变化
• 加入后记得移除，这才方便走其他支线

    public static ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> array = new ArrayList<>();
        if (s == null || s.isEmpty())
            return array;
        ArrayList<String> list = new ArrayList<>();
        partition_s(array, list, s);
        return array;
    }

    public static void partition_s(ArrayList<ArrayList<String>> array, ArrayList<String> list, String s) {
        if (s.length() == 0) {
            //回溯到底了，拷贝list进入array
            array.add(new ArrayList<>(list));
            return;
        }
        int size = s.length();
        for (int i = 1; i <= size; i++) {
            //判断是否是回文
            if (palind(s.substring(0, i))) {
                //是的话先把当前满足回文的子串放入
                list.add(s.substring(0, i));
                //进行回溯
                partition_s(array, list, s.substring(i));
                //移除刚刚添加的元素，也就是回到之前的状态，以便走其他分支
                list.remove(list.size() - 1);
            }
        }
    }

    public static boolean palind(String s) {
        StringBuilder s1 = new StringBuilder(s);
        String s2 = s1.reverse().toString();
        return s.equals(s2);
    }