博客

题目还是有点复杂，难死了，哎、、

利用循环模拟切割，传入开始下标、结束下标

当前取值已经不满足的时候，就不继续dfs了，会有重复的数据。

循环体时判断字符串的

[开始下标，结束下标]

是否满足

回文串。

一旦不满住，后面的递归就可以不进行了，因为会有重复的元素，这点其实很难理解，

所以我是用了更笨的方法，全部加入到list中，收集的时候再判

package lqb;

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

public class likou131 {
    public static void main(String[] args) {
        System.out.println(new likou131().partition("aab"));
    }

    List<List<String>> ans = new ArrayList<>();

    public List<List<String>> partition(String s) {
        char[] arr = s.toCharArray();
        dfs(arr, 0);
        return ans;
    }

    List<String> list = new ArrayList<>();

    private void dfs(char[] arr, int p) {
        if (p == arr.length) {
            if (addCheck(list)) {
                ans.add(new ArrayList<>(list));
            }
            return;
        }
        for (int i = p; i < arr.length; i++) {
            list.add(tostring(arr, p, i));
            dfs(arr, i + 1);
            list.remove(list.size() - 1);
        }
    }

    private boolean addCheck(List<String> list) {
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            char[] arr = s.toCharArray();
            if (!check(arr, 0, arr.length - 1)) {
                return false;
            }
        }
        return true;
    }

    private boolean check(char[] arr, int p, int i) {
        while (p < i) {
            if (arr[p++] != arr[i--]) {
                return false;
            }
        }
        return true;
    }

    private String tostring(char[] arr, int p, int i) {
        String str = "";
        for (int j = p; j <= i; j++) {
            str += arr[j];
        }
        return str;
    }
}

断。