package question;

import java.util.LinkedList;
import java.util.List;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question131 {
 public static void main(String[] args) {
 new Question131().partition("aab").forEach(System.out::println);
 }
 List<List<String>> res;
 public List<List<String>> partition(String s) {
 res = new LinkedList<>();
 f(s, 0, new LinkedList<>());
 return res;
 }

 public void f(String s, int x, LinkedList<String> list) {
 if (x>=s.length()) res.add(new LinkedList<>(list));
 for (int i=1; i<=s.length()-x; i++) {
 String substring = s.substring(x, x + i);
 if (is(substring)) {
 list.add(substring);
 f(s, x+i, list);
 list.removeLast();
 }
 }
 }

 public boolean is(String s) {
 int i=0;
 int j=s.length()-1;
 while (i<j) {
 if (s.charAt(i++)!=s.charAt(j--)) return false;
 }
 return true;
 }
}