Simple DP solution in Python


  • -2
    J
    def checkpd(string):
        return string == string[::-1]
    
    class Solution:
        # @param s, a string
        # @return an integer
     
       def minCut(self, s):
            part = [float('inf') for i in range(len(s)+1)]
            part[0]=-1
            
            for i in range(1,len(s)+1):
                for j in range(1,i+1):
                    if checkpd(s[j-1:i]) and part[i]>part[j-1]+1:
                        part[i]=part[j-1]+1
                        
            return part[-1]
    

    Any suggestions?


Log in to reply
 

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