Cut into palindromes
List every way to cut a string into pieces that each read the same forwards and backwards, by choosing where the first piece ends and recursing on what is left. About 20 minutes.
Choose the first piece
To cut a string, decide where the first piece ends. Any end is possible: one letter, two letters, and so on. The piece is only worth keeping if it is a palindrome, meaning it reads the same in both directions.
After accepting a piece, the rest of the string is the same kind of problem, only shorter.
piece = s[i:j + 1] is_pal = piece == piece[::-1]
First piece a is a palindrome. Continue with bb.
Base case and undo
When the start position reaches the end of the string, the pieces in the current list cover the whole string. Save them, joined by a vertical bar to keep the answer a single text.
After the recursive call returns, remove the piece from the list, so the next end can be tried. A single letter is always a palindrome, so there is always at least one way to cut.
if i == len(s):
out.append("|".join(cur))What happens when a candidate piece is not a palindrome?
- AIt is skipped, and the next longer piece is tried
- BIt is kept, to be fixed later
- CThe whole search stops
Show the answer
It is skipped, and the next longer piece is tried. A cut must have only palindromic pieces.
Palindrome partitioning
Given a string s, return all the ways to cut s into pieces so that every piece is a palindrome. Write each way as its pieces joined by the vertical bar character. List the ways in the order found by trying shorter first pieces before longer ones.
s = "aab" → ["a|a|b", "aa|b"]
1 ≤ length of s ≤ 10 · s has lowercase letters