Problem
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "aab"Output
[["a","a","b"],["aa","b"]]Solution
This solution uses Backtracking to try every possible partition of the string.At each recursion level, the algorithm considers every possible substring starting from the current
start index. If the substring is a palindrome, it is added to the current partition and the recursion continues from the next position.
start index reaches the end of the string, a complete valid partition has been found and is added to the result.
If a substring is not a palindrome, that choice is skipped. After each recursive call, the selected substring is removed so that the algorithm can try the next possible partition.
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(String s, int start,
List<String> current, List<List<String>> result) {
// A complete palindrome partition is found.
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
for (int end = start; end < s.length(); end++) {
// Only choose the substring if it is a palindrome.
if (!isPalindrome(s, start, end)) {
continue;
}
// Choose the palindrome substring.
current.add(s.substring(start, end + 1));
// Continue partitioning from the next position.
backtrack(s, end + 1, current, result);
// Undo the choice.
current.remove(current.size() - 1);
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
Complexity
There can be up to2n - 1 possible ways to partition a string of length n. Checking whether each substring is a palindrome can take up to O(n), resulting in a worst-case time complexity of approximately O(n × 2n).
The recursion depth can be up to
O(n), excluding the space required for storing the output.