Why am I getting TLE for 130ms Runtime


  • 0
    A
    class Solution(object):
    def check(self, s):
        bj = True
        for i in range(len(s)/2):
            if (s[i] != s[len(s)-i-1]):
                bj = False
                break
        return bj
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        indexleft  = 0
        indexright = 0
        ml = 0
        mr = 0
        max = 0
        for i in range(len(s)):
            for j in range(len(s)-1,i,-1):
                if s[i]==s[j]:
                    if self.check(s[i:j+1]):
                        if max<j-i+1:
                            max = j-i+1
                            ml = i
                            mr = j
                        break
        return s[ml:mr+1]
    

    I am getting TLE message from different inputs for several submissions, but as I take them into a normal run, the runtime is around 100ms to 130ms? Is it because of the algorithm or some other problem?


  • 0
    W

    The algorithm looks to be O(n^3), and you can do better than that. The check function takes O(n) time, and it's inside an O(n^2) nested loop. Try improving that and seeing if that helps.


Log in to reply
 

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