Palindrome Partitioning
Medium · Backtracking · String · Dynamic Programming · Backtracking
Problem
Given a string s, cut it into pieces so that every piece is a palindrome (it reads the same forwards and backwards). Return every possible way to do this. Each way is the list of its pieces, in order.
The ways may be returned in any order.
Examples
Input: s = "abba" Output: [["a","b","b","a"],["a","bb","a"],["abba"]]
Single letters always work, "bb" is a palindrome, and so is the whole string.
Input: s = "xy" Output: [["x","y"]]
"xy" is not a palindrome, so only the two single letters work.
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]
"aa" is a palindrome, "aab" and "ab" are not.
Constraints
- 1 <= len(s) <= 16
- s has only lowercase English letters
Approaches
- Baseline: try every set of cuts — time O(n · 2^n), space O(n)
Follow-up
A string of n equal letters has 2^(n-1) partitions, so no algorithm can beat the size of the output; the table only removes the repeated palindrome checks. If you only need a yes or no for exactly three pieces, or how many partitions there are, the table alone answers it in O(n²): those are the use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
