Question about TLE ("aaaaa...")


  • 0
    T

    My idea is quite simple: check whether each substring is a Palindrome using two pointers: start and end. Pointer start is from 0, and end is from len(s) to 0.
    I have two optimizations.
    One is 'end' will alway larger than the previous end 'prevend'.
    Because start increases, if end < prevend, you won't get a longer palindrome
    One is if end == len(s), then stop. Because you find a Palindrome from start to end.

    I use the second one to avoid test case like("aaaa...") case. However, I still has TLE.

    Can anyone help me with this?

    The following is my code.

    class Solution(object):
        def isPalindrome(self, s, start, end): #Test s[start:end] is Palindrome or not.
            if start > end :
                return False
            i = start
            j = end - 1
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True
                
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            start = 0
            longPalindrom = ""
            maxlen = 0 
            preend = 0  # save previous end 
            while start < len(s):
                end = len(s)
                # find longest palindrome begins s[start] 
                while not self.isPalindrome(s, start, end) and end > preend: 
                    end -= 1
                preend = end 
                if maxlen < end - start:
                    longPalindrom = s[start:end]
                    maxlen = end - start
                if end == len(s): # second optimization
                    break
                start += 1
            return longPalindrom
    

Log in to reply
 

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