Palindrome Partitions

A palindrome reads the same forwards and backwards, like "level" or "a". Write palindrome_partitions(s) that returns every way to cut the string s into consecutive pieces so that every piece is a palindrome.

Each way is a list of its pieces in order. Return the list of ways sorted, in Python's ordering of lists, which compares the pieces one by one.

Examples

palindrome_partitions("aab")  # returns [['a', 'a', 'b'], ['aa', 'b']]
palindrome_partitions("racecar")
# returns [['r', 'a', 'c', 'e', 'c', 'a', 'r'], ['r', 'a', 'cec', 'a', 'r'], ['r', 'aceca', 'r'], ['racecar']]
palindrome_partitions("abc")  # returns [['a', 'b', 'c']]

Single letters are always palindromes, so cutting s into its letters is always one of the answers.

Constraints

• 1 <= len(s) <= 16
• s holds lowercase letters only.