Palindrome Partitioning

Return every way to cut s into pieces so that every piece is a palindrome (reads the same both ways). Each way is a list of the pieces from left to right. List the ways sorted as lists of strings (compare the first piece, then the second, and so on).

For "aab": ["a", "a", "b"] and ["aa", "b"].

Examples

Example 1

Input:

palindrome_partitions('aab')

Output:

[['a', 'a', 'b'], ['aa', 'b']]

Example 2

Input:

palindrome_partitions('a')

Output:

[['a']]

Constraints

• 0 <= len(s) <= 14
• s contains lower-case letters.