A helper table, then a smaller decision
Pre-compute which ranges are palindromes, then decide the fewest cuts using that lookup. About 13 minutes.
First, know which pieces are palindromes
You want to cut a word into pieces that each read the same backwards, using as few cuts as possible. "aab" needs one cut: "aa" and "b".
Start by answering a simpler question for every piece of the word: is it a palindrome? A single letter always is. A longer piece is a palindrome when its two end letters match and the piece between them is a palindrome too. That's a question about a shorter piece, so work from short pieces to long ones.
Then, the fewest cuts so far
Now walk along the word. For each position, ask: what's the fewest cuts that turns everything up to here into palindromes?
If everything up to here is already a palindrome, that's 0 cuts. Otherwise, try every place the last piece could start. If that last piece is a palindrome, it costs one cut plus the fewest cuts for everything before it. Keep the smallest.
cuts = [0] * len(s) cuts[end] = 0 # a whole palindrome
Every single letter is a palindrome.
In "aab", the pieces "a", "a", "b" and "aa" are palindromes, but "aab" isn't. What's the fewest cuts for the whole word?
- A1
- B0
- C2
Show the answer
1. Cut after "aa": "aa" and "b" are both palindromes.
Minimum cuts for a palindrome partition
Given a string s, return the fewest cuts needed to split it into pieces that are each a palindrome. A string with no cuts needs 0 if it's already a palindrome.
s = "aab" → 1
0 ≤ s.length ≤ 1,000 · lowercase English letters