[python][solved] Time Limit Exceeded


  • 0
    Z

    i used DP to solve the problem, but when encontered the last test case,it always throw out the TLE, how can i optimize the code?

    my code:

    class Solution:
      def minCut(self,s):
        length=len(s)
    
        is_palindrome=[[False for _ in xrange(length)] for _ in xrange(length)]
        for sublen in xrange(1,length+1):
          for substart in xrange(0,length):
            subend=substart+sublen-1 #here subend always bigger than substart!!
            if subend>length-1:subend=length-1
            if substart==subend:
              is_palindrome[substart][subend]=True
              continue
            if (substart+1)==subend:
              is_palindrome[substart][subend]= (s[substart]==s[subend])
              continue
            is_palindrome[substart][subend]= (s[substart]==s[subend])and is_palindrome[substart+1][subend-1]
            
        if is_palindrome[0][length-1]:return 0
        
        DP_minCut=[length for _ in xrange(length)]
    
        for i in xrange(0,length):
          if is_palindrome[0][i]:
            DP_minCut[i]=0
            continue
          for j in xrange(1,i+1):
            if is_palindrome[j][i]:
              DP_minCut[i]=min(DP_minCut[i],DP_minCut[j-1]+1 )
        return    DP_minCut[-1] 
        
    s=Solution()
    print s.minCut("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")

  • 0
    Z

    i have solved this question,the loops to finish the is_palindrome table have some performance waste.

    here is my optimized code:

    class Solution:
      def minCut(self,s):
        length=len(s)
        is_palindrome=[[False for _ in xrange(length)] for _ in xrange(length)]
        
        for sublen in xrange(1,length+1):
          for substart in xrange(0,length-sublen+1):
            subend=substart+sublen-1 # subend >= substart
            
            if substart==subend:
              is_palindrome[substart][subend]=True
              continue
    
    
            if sublen==2:
              is_palindrome[substart][subend]= s[substart]==s[subend]
              continue
    
            is_palindrome[substart][subend]= (s[substart]==s[subend])and is_palindrome[substart+1][subend-1]
            
        if is_palindrome[0][length-1]:return 0
    
        DP_minCut=[length for _ in xrange(length)]
        
        for i in xrange(0,length):
          if is_palindrome[0][i]:
            DP_minCut[i]=0
            continue
          for j in xrange(1,i+1):
            if is_palindrome[j][i]:
              DP_minCut[i]=min(DP_minCut[i],DP_minCut[j-1]+1 )
              if DP_minCut[length-1]<=1:return DP_minCut[length-1]
              if DP_minCut[i]<=1:
                break
    
        
        return DP_minCut[length-1] 
    

    another solution:

    class Solution:
      def minCut(self,s):
        length=len(s)
        is_palindrome=[[False for _ in xrange(length)] for _ in xrange(length)]
        DP_minCut=[length for _ in xrange(length)]
        
    
        for i in xrange(0,length):
          for j in xrange(0,i+1):
            if (s[j]==s[i])and((is_palindrome[j+1][i-1] if (i>0 and j<length-1 )else False) or i-j<2):
              is_palindrome[j][i]=True
              if j==0:DP_minCut[i]=0
              DP_minCut[i]=min(DP_minCut[i],DP_minCut[j-1]+1)
    
    
    
        return DP_minCut[-1]
    

  • 0
    S

    I copy and paste your code to the judge but seems it still TLE...


  • 0
    P

    Doesn't work. Also TLE with Last executed input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"


Log in to reply
 

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