Palindrome Partitioning
The key idea
Walk left to right and try every possible prefix as the next piece. A prefix may join the current partition only if it is a palindrome. Recurse on the remaining suffix, then undo the choice and try a longer prefix. The chosen pieces always cover the string with no gaps.
Problem
Given a string s, partition s so that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s. A palindrome is a string that reads the same forward and backward, such as aba or aa. You may return the partitions in any order.
Constraints
1 <= s.length <= 16scontains only lowercase English letters
Examples
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Input: s = "aba"
Output: [["a","b","a"],["aba"]]
Input: s = "a"
Output: [["a"]]
Complexity
Time: O(n * 2^n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- CombinationsMEDIUM
- Generate ParenthesesMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-QueensHARD
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM
- PermutationsMEDIUM