Split Into Palindromes
Problem
Cut a string into pieces so that every piece reads the same forwards and backwards. Return every way of doing that, with each way given as the list of pieces in order. Single characters count as palindromes, so at least one cutting always exists.
Examples
Input: s = "aab"
Output: [["a", "a", "b"], ["aa", "b"]]
Why: "ab" is not a palindrome, so no cutting starts with itInput: s = "aaa"
Output: 4 cuttings
Why: "a|a|a", "aa|a", "a|aa" and "aaa" all qualifyInput: s = "a"
Output: [["a"]]
Why: edge case, a single character is already a palindromeHints
0 / 3
The first cut decides everything after it. Ask what is left to solve once that first piece is chosen.
At each position the branches are the possible lengths of the next piece. Most of them are dead on arrival.
Recurse on the index where the next piece starts. For each end position, test the slice and skip it unless it reads the same backwards, then recurse from that end. When the start reaches the end of the string, record a copy of the path.
Solution
The start index is the whole state: everything before it is already cut, everything from it onwards is a smaller copy of the same problem. Each branch is a candidate next piece, and the palindrome test rejects a branch before any recursion happens underneath it, which is what keeps the search away from most of the two to the n-1 possible cuttings. Reaching the end of the string means the path is complete, so it is copied out. Worst case, on a string of identical characters, time is O(n times 2 to the n).
def palindrome_splits(s):
out = []
def build(start, path):
if start == len(s): # the whole string is cut up
out.append(path[:])
return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if piece != piece[::-1]: # not a palindrome: prune the branch
continue
path.append(piece) # choose
build(end, path) # explore
path.pop() # un-choose
build(0, [])
return out
print(palindrome_splits("aab")) # -> [['a', 'a', 'b'], ['aa', 'b']]
print(len(palindrome_splits("aaa"))) # -> 4
print(palindrome_splits("a")) # -> [['a']]Stuck on the idea rather than the code? Word Search & Pruning covers it.