package num2;

import java.util.ArrayList;

/**

* @author PC

* @program basic-code

* @description

* @create: 2021-01-25 20:09

**/

public class test1 {

public static void main(String[] args) {

String s = "aabcbaa";

ArrayList<ArrayList<String>> ans = partition(s);

for (ArrayList<String> str : ans) {

System.out.println(str);

}

}

//获得一个字符串的所有回文子串集合

public static ArrayList<ArrayList<String>> partition(String s) {

ArrayList<ArrayList<String>> arr = new ArrayList<ArrayList<String>>();

if (s == null || s.length() == 0) {

return arr;

}

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

dfs(0, s, list, arr);

return arr;

}

// 回溯法

private static void dfs (int index, String s, ArrayList<String> prelist, ArrayList<ArrayList<String>> arr) {

if (index == s.length()) {

arr.add(new ArrayList<String>(prelist));

return;

}

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

for (int i = index; i != s.length(); i++) {

if (isHui(s, index, i)) {

list.add(s.substring(index, i + 1));

dfs(i + 1, s, list, arr);

list.remove(list.size() - 1);

}

}

}

// 判断是否为回文串

private static boolean isHui(String s, int start, int end) {

while (start <= end) {

if (s.charAt(start++) != s.charAt(end--)) {

return false;

}

}

return true;

}

}