LeetCode Q132: Palindrome Partitioning II (hard)

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution:

Using DP. No need to check whether a sub-string is a palindrome or not. At each character, we check its two sides to see if characters are the same. Need to take into account odd length palindrome and even length palindrome.

I'd like to help explain this great algorithm. :-O

This divide-and-conquer algorithm utilize the symmetry of palindromes, so there is no need to cache the result of whether s[i:j) is a palindrome.

Say that it started at s[i] = 'b', and s[i-1,i+1] is a palindrome "aba":

.......aba...
|<-x-><-x->| ^
|<---y--><---y-->|

And we know the least cuts for s[0,i-1) is X, then the least cuts for s[0,i+1] Y is not greater than X+1. Last, we need to find out all the palindromes in s[0,i+1] so as to minimize the number of cuts.