Enumerate palindromic decompositions PalindromePartitioning.java
public static List<List<String>> palindromePartitioning(String s) {
List<List<String>> result = new ArrayList<>();
List<String> partition = new ArrayList<>();
palindromePartitioningHelper(s, 0, partition, result);
return result;
}
private static void palindromePartitioningHelper(String s, int begin,
List<String> partition,
List<List<String>> result) {
if (begin == s.length()) {
result.add(new ArrayList<>(partition));
return;
}
for (int i = begin + 1; i <= s.length(); ++i) {
String prefix = s.substring(begin, i);
if (isPalindrome(prefix)) {
partition.add(prefix);
palindromePartitioningHelper(s, i, partition, result);
partition.remove(partition.size() - 1);
}
}
}
private static boolean isPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
