Palindrome Partition II

Question

Given a string s, cut s into some substrings such that every substring is a palindrome.

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

Thoughts

可以用palindrom partition I的方法，得到所有results后算一个最小的cut number 不过在lintcode上memory limit exceeds

Dynamic Programming的思路 csdn blog

DP解法

用一个matrix[][]来存palindrom 的结果，matrix[i][j]为true表示substring(i, j)是一个palindrome 另一个list cuts[]来存从当前点到end需要的cuts数，比如cuts[i]表示substring(i:)需要的最小cuts 初始化cuts[i] = len-1-i, 所以最终的结果应该就是cuts[0]

Solution

Memory limit exceeds版本

class Solution:
    # @param s, a string
    # @return an integer
    def __init__(self):
        self.results = []

    def minCut(self, s):
        self.partitionHelper(s, [])
        numMinCut = self.getMinCut(self.results)
        return numMinCut

    def getMinCut(self, results): 
        numMin = sys.maxint
        for cuts in self.results:
            num = len(cuts) - 1
            if num < numMin:
                numMin = num
        return numMin


    def partitionHelper(self, s, result):
        if not s:
            """
            have to create to a new list
            otherwise it would change, list is mutable
            """
            x = list(result)
            self.results.append(x)
        for i in range(len(s)):
            if self.isPalindrome(s, i):
                result.append(s[:i+1])
                self.partitionHelper(s[i+1:], result)
                result.pop()

    def isPalindrome(self, s, i):
        start = 0
        while start < i:
            if s[start] != s[i]:
                return False
            start += 1
            i -= 1 
        return True

DP

# -*- coding: utf-8 -*-                                                                                                                   
class Solution:       
    # @param s, a string
    # @return an integer

    def minCut(self, s):
        if not s:     
            return 0  
        """ 
        cuts的初始值要注意
        """          
        cuts = [(len(s)-i-1) for i in range(len(s))]
        matrix = [[False for i in range(len(s))] for j in range(len(s))]
        for i in range(len(s)):
            matrix[i][i] = True
        print cuts   
        print matrix 
        """          
        Note:        
        应该从后往前loop，这样才能更新前面的值，越后面的值越早,前面的cuts[i]需要用到后面的cuts[j]
        """          
        for i in range(len(s), -1, -1):
            for j in range(i, len(s)):
                """  
                Two cases:
                1. i, j neighbour, i = j or i + 1 = j
                2. j - i >= 2, can use matrix
                """  
                if s[i] == s[j] and j-i<2 or s[i] == s[j] and matrix[i+1][j-1]:
                    print "i: " + str(i)
                    print "j: " + str(j)
                    matrix[i][j] = True
                    #越前面需要的cuts可能越多，所以这样set
                    if j != len(s)-1:
                        cuts[i] = min(cuts[i], cuts[j + 1] + 1)
                    else:
                        cuts[i] = min(cuts[i], 0)
                    print cuts
        minCuts = cuts[0]
        return minCuts