My accepted simple DP python solution

  • 2
    class Solution(object):
        def minCut(self, s):
            :type s: str
            :rtype: int
            n = len(s)
            dp = [(i-1) for i in range(n+1)]
            for i in range(1,n+1):
                for j in range(i):
                    temp = s[j:i]
                    if temp[:] == temp[::-1]:
                        dp[i] = min(dp[i],dp[j] + 1)
            return dp[n]

  • 0

    Consider s=''

  • 0

    This solution isn't accepted anymore. It gives TLE for a very long string.

Log in to reply

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