Palindrome Partitioning II

题目描述

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.

解题方法

DFS + backtracking

这一题用1的做法求出所有解，再找出长度最小的是可以的，不过会有很多重复计算

DP

这种找min，max的题目我们可以往DP的方向想。

  1. state

    minCut[i]表示s[:i+1]的最小minCut是多少

  2. function

    minCut[i] = minCut[j] + 1 if isPalindrome(s[j:i+1]) == True

  3. result

    minCut[len(s)]

Solution

class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return

        length = len(s)

        matrix = [[False for i in range(length)] for j in range(length)]
        minCut = [sys.maxint for i in range(length)]
        minCut[0] = 0

        for i in range(length):
            matrix[i][i] = True

        for i in range(1, length):
            for j in range(i+1):
                if (s[i] == s[j] and i - j < 2) or (s[i] == s[j] and matrix[j+1][i-1]):
                    matrix[j][i] = True
                    if j == 0:
                        minCut[i] = 0
                    else:
                        minCut[i] = min(minCut[i], minCut[j-1] + 1)

        return minCut[length-1]

Reference