My python solution


  • 0
    Q
    class Solution(object):
        def minCut(self, s):
            """
            :type s: str
            :rtype: int
            """
            if s is None or len(s) <= 1:
                return 0
            m = len(s)
            dp = [[False] * m for i in xrange(m)]
            for width in xrange(m):
                for i in xrange(m - width):
                    j = i + width
                    dp[i][j] = (width <= 1 or dp[i + 1][j - 1]) and s[i] == s[j]
            dpp = [-1] * (m + 1)
            for i in xrange(m):
                minvalue = i
                for j in xrange(i + 1):
                    if dp[j][i]:
                        minvalue = min(minvalue, dpp[j])
                dpp[i + 1] = minvalue + 1
            return dpp[-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.