Implement the palindromePartitionMinCuts method that returns the minimum cuts needed to split text into palindrome parts.
The input contains a string text. Your task is to split the string into substrings so that every substring is a palindrome, and return the minimum number of cuts needed.
A palindrome substring reads the same from left to right and right to left.
For example, aab can be split as aa|b. Both parts are palindromes, so only 1 cut is required.
Example 1
aab1Example 2
a0Example 3
ab1First identify which substrings are palindromes, then use dynamic programming to calculate the minimum cuts.
Create a palindrome table where pal[start][end] is true when the substring from start to end is a palindrome. This avoids checking the same substring again and again.
Then calculate cuts[end], the minimum cuts needed for the prefix ending at end. If the whole prefix is already a palindrome, the cut count is 0. Otherwise, try every valid previous palindrome part and keep the minimum.
Pseudocode:
function palindromePartitionMinCuts(text):
n = length of text
create palindrome table pal[n][n] with false values
for end from 0 to n - 1:
for start from 0 to end:
if text[start] == text[end] and (end - start < 2 or pal[start + 1][end - 1]):
pal[start][end] = true
create cuts array of size n
for end from 0 to n - 1:
if pal[0][end] == true:
cuts[end] = 0
else:
cuts[end] = end
for start from 1 to end:
if pal[start][end] == true:
cuts[end] = minimum(cuts[end], cuts[start - 1] + 1)
return cuts[n - 1]