Why also TLE at "aaa……..aaaaa" [Python]


  • 0
    L

    my solution is a force one,testing the substring by different length for len(s) to 1.BUT always TLE at "aaaa…aaaa", i think for this case my method is O(n) ,and i tried to avoid the "aaaa….aaaa" case:

    if s.startswith("aaaa") :
        return s
    

    And, got the same result . Anyone knows the reason? thx~~

    class Solution:
            # @return a string
            def longestPalindrome(self, s):
                i = length = len(s)
                for i in range(i,1,-1):      # i is the length for the current testing substring
                    for j in range(0,length-i+1): # j is the start point of the substring
                        pos_start = start = j
                        pos_end = end = j + i - 1
                        while start <= end :
                            if s[start] == s[end]:
                                start += 1
                                end -= 1
                            else:
                                break
                        if start > end :  
                            if i == length:  # just to avoid creating a new substring 
                                return s
                            else:
                                new_str = s[pos_start:pos_end+1]
                                return new_str

  • 0
    L

    I have the same problem. Came up with O(n^2), but got TEL error with the "aaaaaaaaaaaaaa...." string.


  • 1
    P

    My DP solution with O(n^2) also fail to pass due to TLE in the case of string: "esbtzjaaijqkgmtaajpsdfiqtvxsgfvijpxrvxgfumsuprzlyvhclgkhccmcnquukivlpnjlfteljvykbddtrpmxzcrdqinsnlsteonhcegtkoszzonkwjevlasgjlcquzuhdmmkhfniozhuphcfkeobturbuoefhmtgcvhlsezvkpgfebbdbhiuwdcftenihseorykdguoqotqyscwymtjejpdzqepjkadtftzwebxwyuqwyeegwxhroaaymusddwnjkvsvrwwsmolmidoybsotaqufhepinkkxicvzrgbgsarmizugbvtzfxghkhthzpuetufqvigmyhmlsgfaaqmmlblxbqxpluhaawqkdluwfirfngbhdkjjyfsxglsnakskcbsyafqpwmwmoxjwlhjduayqyzmpkmrjhbqyhongfdxmuwaqgjkcpatgbrqdllbzodnrifvhcfvgbixbwywanivsdjnbrgskyifgvksadvgzzzuogzcukskjxbohofdimkmyqypyuexypwnjlrfpbtkqyngvxjcwvngmilgwbpcsseoywetatfjijsbcekaixvqreelnlmdonknmxerjjhvmqiztsgjkijjtcyetuygqgsikxctvpxrqtuhxreidhwcklkkjayvqdzqqapgdqaapefzjfngdvjsiiivnkfimqkkucltgavwlakcfyhnpgmqxgfyjziliyqhugphhjtlllgtlcsibfdktzhcfuallqlonbsgyyvvyarvaxmchtyrtkgekkmhejwvsuumhcfcyncgeqtltfmhtlsfswaqpmwpjwgvksvazhwyrzwhyjjdbphhjcmurdcgtbvpkhbkpirhysrpcrntetacyfvgjivhaxgpqhbjahruuejdmaghoaquhiafjqaionbrjbjksxaezosxqmncejjptcksnoq"

    class Solution:
        # @return a string
        def longestPalindrome(self, s):
            
            size = len(s)
            
            if size==0:
                return ""
            
            record = [[False for i in range(size)] for i in range(size)]
            max_len = 0
            start = -1
            end = -1
    
            for i in range(size):
                for j in range(0,i):
    
                    ok = False
                    if i==j+2:
                            if s[i]==s[j]:
                                    ok = True
                    if i==j+1:
                            if s[i]==s[j]:
                                    ok = True
                    else:
                            if record[j+1][i-1] and s[i]==s[j]:
                                    ok = True
    
                    record[j][i] = ok
    
                    if ok and i-j+1>max_len:
                            max_len = i-j+1
                            start = j
                            end = i
    
                record[i][i] = True
                
            return s[start:end+1]    
    

    I suspect that might due to the natural performance issue of python, I'm trying the same implementation with Java now.... (Otherwise, we might need to use O(n) solution such as http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html for python to pass on leetcode )


  • 0
    S

    It seems if you got a TLE, it only means the total time exceeds the limit. You code just happens to run to "aaaa" test case.


Log in to reply
 

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