My accepted simple DP python solution


  • 2
    X
    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
    C

    Consider s=''


  • 0
    L

    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.