Palindrome Partitioning
MediumBacktracking
Given a string s, return every way to cut it into pieces so that every piece is a palindrome (reads the same forwards and backwards).
- Each piece is a non-empty, contiguous substring, and the pieces in order must join back into
s. - Each partition is a list of pieces in left-to-right order.
- Return the partitions themselves in any order, each exactly once.
Example 1
- Input:
- s = "abba"
- Output:
- [["a","b","b","a"],["a","bb","a"],["abba"]]
- Explanation
- Single letters always work.
bbis a palindrome, so it can stay together, and the whole stringabbais a palindrome too. Cuts likeab|bafail becauseabis not a palindrome.
Example 2
- Input:
- s = "xyx"
- Output:
- [["x","y","x"],["xyx"]]
- Explanation
- Either every letter on its own, or the whole string, since
xyxreads the same backwards.xyandyxare not palindromes.
Example 3
- Input:
- s = "abc"
- Output:
- [["a","b","c"]]
- Explanation
- No two neighbouring letters match, so the only option is to cut between every letter.
Constraints
1 <= s.length <= 16sconsists of lowercase English letters