Why TLE?


  • 0
    C

    Thanks. I did the same algorithm in Java, which accepted. Why my python codes not accepted?

    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            if not s: 
                return ''
                
            L = len(s)
            
            if L==0 or L==1: 
                return s
    
            dp = [ [False for i in range(0, L)] for j in range(0, L) ]
            for i in range(0, L):
                dp[i][i] = True
            maxLen = 1
            start = 0
            #print 1, dp, start, maxLen
            
            for i in range(1, L):
                if s[i]==s[i-1]: 
                    dp[i-1][i] = True
                    if maxLen < 2: 
                        start = i-1
                        maxLen = 2
            #print 2, dp, start, maxLen
                
            for l in range(3, L+1):
                for i in range(0, L-l+1):
                    if dp[i+1][i+l-2] and s[i]==s[i+l-1]:
                        dp[i][i+l-1]=True
                        if maxLen< l:
                            start = i
                            maxLen = l
                            
            return s[start:start+maxLen]
    
    

  • 0
    E

    Same deal here. I have my python code with the time complexity is being O(n^2), when running OJ, it just got TLE. It should be work with O(n^2), right? The same time complexity with C++ is accepted by OJ.

    my python code:

    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            max_left = 0
            max_right = 0
    
            for i in xrange(2*len(s)):
                left = i
                right = i
    
                while left >= 0 and right < 2*len(s):
                    if left%2 == 0 and s[left/2] != s[right/2]:
                        break
                    left -= 1
                    right +=1
    
                left += 1
                right -= 1
    
                real_left = (left + left%2)/2
                real_right = right/2 + 1
    
                if (real_right - real_left) > (max_right - max_left):
                    max_left = real_left
                    max_right = real_right
    
            return s[max_left:max_right]
    
    

    I got Runtime: 192 ms with the case:
    "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffgggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"

    Same case running with the solution here:
    https://discuss.leetcode.com/topic/65388/straightforward-python-solution
    is Runtime: 89 ms.

    So I am curious what is the criteria here?


  • 0
    E

    @Chengcheng.Pei

    hmm, I got an explanation from here:
    http://stackoverflow.com/questions/801657/is-python-faster-and-lighter-than-c
    saying that Python is on the order of between 10 and 100 times slower than C++ at running time.

    seems like Python is slower that Java too
    http://stackoverflow.com/questions/3044620/python-vs-java-performance-runtime-speed

    I ran your python code with the case:
    "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffgggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"

    It took Runtime: 259 ms
    What is the running time of the same case in Java?


Log in to reply
 

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