A cut is defined as a slice of a string that partitions a string into two. Given a string, return the minimum number of cuts required to partition the string into palindromic substrings.
a would return 0, since
a is already a palindrome and no cuts are required.
asa would also return 0, since
asa is also a palindrome.
as would return 1, since one cut is required:
aasaadl would return 2:
The solution is a brilliant usage of dynamic programming - one of those times where you’re completely stuck at first but seems so obvious once you know it.
What we’re memoizing is the number of cuts required for each of the prefixes, and running mid-point checks from each of the starting points (not forgetting to take both odd and even length palindromes into account). Running time is quadratic in the length of the string, and space required is linear.
As you can see, when we detect a palindrome, we update the
cuts array with a previous value of
cuts (which we already know to be optimal) + 1.
def minimum_palindrome_partitions(s): # cuts[i] = how many palindrome partitions required to cut s[:i] # we initialize it as i-1 first since that's the maximum number of cuts possibly required (if all characters are distinct) cuts = [i-1 for i in range(len(s) + 1)] # check each center of palindrome candidate for i in range(len(s)): # at each center, check odd length palindromes for j in range(min(i + 1, len(s) - i)): if s[i - j] == s[i + j]: cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j] + 1) else: break # at each center, check even length palindromes for j in range(min(i, len(s) - i)): if s[i - j - 1] == s[i + j]: cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j - 1] + 1) else: break return cuts[-1]