Palindrome Partition II

The main idea for the algorithm is that if s[i:j] is a palindrome, minCut(s[:j]) is at most minCut(s[:i]) plus one. For example, for string "abcracecar", "racecar" is a palindrome, thus min cut for the whole string is actually min cut for "abc" plus 1 by cut between "c" and "r".

Based on this, we can design an dynamic-programming algorithm that first check whether a substring is palindrome and then get its min cut. Also we need to initialize the dp list as the length of sub-string and do dynamic program from the head of the string till the end.

Code in Python:

class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = [i for i in xrange(-1, len(s))]
        for i in xrange(len(s)):
            r1, r2 = 0, 0
            while i-r1 >= 0 and i+r1 < len(s) and s[i-r1] == s[i+r1]:
                dp[i+r1+1] = min(dp[i+r1+1], dp[i-r1]+1)
                r1 += 1
            while i-r2 >= 0 and i+r2+1 < len(s) and s[i-r2] == s[i+r2+1]:
                dp[i+r2+2] = min(dp[i+r2+2], dp[i-r2]+1)
                r2 += 1
        return dp[-1]