Palindrome Partitioning
Given a string `s`, partition `s` such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of `s`.
Examples
Constraints
1 <= s.length <= 16`s` contains only lowercase English letters.
Backtracking
Approach
We explore all possible partitions of the string using backtracking. At each step, we iterate through the remaining string from the current `start` index to the `end`. If the substring from `start` to `i` is a palindrome, we add it to our current partition list and recursively call the backtrack function for the remaining substring (starting at `i + 1`). If we reach the end of the string, it means we have found a valid partition, which we add to our result.
Complexity Analysis
In the worst case (e.g., all characters are the same like "aaaa"), there are 2^(n-1) possible partitions. For each partition, creating the substring takes O(n) time. The space complexity is O(n) for the recursion stack and the current list.
class Solution { public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); backtrack(0, s, new ArrayList<>(), result); return result; } private void backtrack(int start, String s, List<String> current, List<List<String>> result) { // Base case: we have processed the entire string if (start == s.length()) { result.add(new ArrayList<>(current)); return; } // Explore all possible substrings starting from 'start' for (int i = start; i < s.length(); i++) { // Check if substring s[start...i] is a palindrome if (isPalindrome(s, start, i)) { current.add(s.substring(start, i + 1)); // Recurse for the remaining part of the string backtrack(i + 1, s, current, result); // Backtrack 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; } left++; right--; } return true; }}