Why my approach TLE? I guess it should be O(n^2)


  • 0
    C
    def longestPalindrome(s):
        length = len(s)
                
        isPalindrome = []
        for i in range(length):
            isPalindrome.append([False] * length)
        
        for i in reversed(range(length)):
            for j in reversed(range(i, length)):
                if s[i] == s[j]:
                    if (j - i) <= 1:
                        isPalindrome[i][j] = True
                    else:
                        isPalindrome[i][j] = isPalindrome[i + 1][j - 1]
                else:
                    isPalindrome[i][j] = False
        
        maxStr = s[0]
        for i in range(length):
            for j in range(i, length):
                if isPalindrome[i][j]:
                    pLen = j - i + 1
                    if pLen > len(maxStr):
                        maxStr = s[i:j + 1]
                    
        return maxStr

Log in to reply
 

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