All problems

Palindrome Partitioning

Medium · backtracking

Given a string s, cut it into one or more pieces so that every piece is a palindrome (it reads the same forwards and backwards). Return every way of doing this.

A way of cutting is a list of the pieces from left to right, so joining them together gives back s exactly. Two ways are different if they cut s at different places. A piece of a single character is always a palindrome. The ways may be returned in any order.

Examples

Example 1

Input: s = "aab"

Output: [["a", "a", "b"], ["aa", "b"]]

"aab" itself is not a palindrome, and "ab" is not either, so the last piece must be "b" on its own.

Example 2

Input: s = "level"

Output: [["l", "e", "v", "e", "l"], ["l", "eve", "l"], ["level"]]

"eve" and "level" are palindromes longer than one letter, which gives the extra ways.

Example 3

Input: s = "xy"

Output: [["x", "y"]]

Constraints

• 1 <= len(s) <= 12
• s contains only lowercase English letters.