Medium Backtrack+Prune Backtracking
In plain English: Split a string into pieces where every piece reads the same forwards and backwards.
Try every prefix as a palindrome candidate. If valid, recurse on the remaining suffix. Backtrack when no valid palindrome prefix exists.
Prompt
Given a string s, partition it such that every substring is a palindrome. Return all possible partitions.
Try to write it from scratch before scrolling down.
Solution
def palindrome_partition(s):
result = []
def is_pal(sub):
return sub == sub[::-1]
def backtrack(start, path):
if start == len(s):
result.append(path[:])
return
for end in range(start + 1, len(s) + 1):
sub = s[start:end]
# prune: only recurse when prefix is a palindrome, skipping invalid branches early
if is_pal(sub):
path.append(sub)
backtrack(end, path)
path.pop() # undo choice so sibling branches start clean
backtrack(0, [])
return result
# Test: palindrome_partition("aab") == [["a","a","b"],["aa","b"]]