Palindrome Partitioning
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Split a string into pieces so that every piece is a palindrome. Return all ways.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What are the possible first pieces of "aab"? Which are palindromes?
- Hint 2After choosing a first piece, the rest is the same problem on a shorter string.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Cutting a string of beads into necklaces, where each piece must read the same forwards and backwards. At the start of the remaining beads, try a first piece of length 1, then 2, then 3... Keep a piece only if it is a palindrome, and then cut the remaining beads the same way. Reaching the end gives one complete way.
- The obvious way
Try all 2^(n-1) cut patterns and check every piece: the same count, backtracking just prunes early.
- The key insight
Recursive function cut(start): if start reaches the end, save the current pieces. Otherwise, for each end after start, take the piece start..end; if it is a palindrome, add it to the pieces, call cut(end), then remove it.
- The algorithm
- pieces = []; cut(0).
- At the end of the string: save a copy of pieces.
- Otherwise try each piece from start; keep only palindromes.
- Add, recurse from the piece end, remove.
Watch it run
Examples = "aab"
First piece "a" is a palindrome. Continue with "ab": piece "a" works, then "b" works. Way: a | a | b.
found: [a, a, b]
Where people slip
- Loop end up to len(s) inclusive: the last piece must be allowed to reach the end.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def partition(s):
result = []
pieces = []
def cut(start):
if start == len(s):
result.append(list(pieces)) # the whole string is cut
return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if piece == piece[::-1]: # reads the same both ways
pieces.append(piece)
cut(end)
pieces.pop() # backtrack
cut(0)
return resultNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.