Palindrome Partitioning
Given a string s, split it into contiguous pieces so that every piece is a palindrome (reads the same forwards and backwards), and return all possible such splits. Every character must belong to exactly one piece, and pieces keep their original order.
The string is at most 16 characters of lowercase letters, so an exponential number of partitions is expected — there are up to 2^(n−1) ways to cut a string of length n.
Examples
- Input:
- s = "aab"
- Output:
- [["a", "a", "b"], ["aa", "b"]]
Cutting after each letter gives three single-letter palindromes. Taking "aa" as one piece also works. "aab" itself and "ab" are not palindromes, so no other split qualifies.
- Input:
- s = "a"
- Output:
- [["a"]]
A single character is trivially a palindrome; there is only one way to split it.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.