package com.example.leetcode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
static boolean isPalindrom(char[] s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
public static List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
Deque<String> path = new ArrayDeque<>();
backtracking(s.toCharArray(), 0, res, path);
return res;
}
static void backtracking(char[] s, int startIndex, List<List<String>> res, Deque<String> path) {
if (startIndex == s.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < s.length; i++) {
if (isPalindrom(s, startIndex, i)) {
path.addLast(new String(s,startIndex, i - startIndex + 1));
} else {
continue;
}
backtracking(s, i + 1, res, path);
path.removeLast();
}
}
public static void main(String[] args) {
String s = "aab";
List<List<String>> res = partition(s);
res.forEach(m -> {
for (String r : m) {
System.out.print(r + "");
}
System.out.println();
});
System.out.println();
}
}