Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Palindrome Partitioning

LeetCode #131Medium
Cut only where the prefix is a palindrome

Given a string, return all ways to partition it into contiguous substrings such that every substring is a palindrome.

Asked atAmazonGoogle
step 1 / 25
cut only where the prefix is a palindrome
a|a|b
a|a
a|ab
a
aa|b
aa
aab
ε
partitions
(none yet)
Backtracking · cut on palindrome prefixes only
▸
1partition(pos, parts):
2    if pos == len(s): record parts; return  // reached the end
3    for end in pos+1..len(s):
4        prefix = s[pos..end]
5        if not isPalindrome(prefix): prune; continue
6        parts.push(prefix)                  // choose
7        partition(end, parts)               // explore
8        parts.pop()                         // un-choose
9    return
10// answer = all recorded partitions
state
  • s"aab"
  • goalall-palindrome partitions

line 1Partition "aab" so every piece is a palindrome. We scan left to right; at each position we try cutting off a prefix of length 1, 2, 3 … Each cut is a choice, so the partitions form a tree. Labels show the partition so far, "a|a" meaning two pieces "a" and "a".