Palindrome Partitioning
Problem
Cut a string into pieces so that every piece reads the same forwards and backwards. Return every such way of cutting it.
Examples
Constraints
- • 1 <= s.length <= 16
- • s has only lowercase English letters
Hints & approach
Hint 1
Decide where the first piece ends, then solve the rest of the string the same way.
Hint 2
Only recurse when the chosen first piece is a palindrome.
Hint 3
Precompute a table isPal[i][j] to make each check O(1).
Approachtry the hints first
Backtrack over the start index. From start, try every end index; if s[start..end] is a palindrome, push it, recurse from end + 1, then pop. When start reaches the end of the string, the current list of pieces is a valid partition. Checking palindromes can be made O(1) by filling a DP table where isPal[i][j] is true when s[i] == s[j] and the inside is a palindrome. In the worst case (all same letters) there are 2^(n-1) partitions.
Time O(n * 2^n) · Space O(n^2) for the palindrome table