Why O(n^2) also TLE for Longest Palindromic Substring


  • 0
    C

    Could somebody can point where should I improve?
    {

    class Solution:
    # @return a string
    def longestPalindrome(self, s):
        if s == '':
            return ''
        res = s[0]
        longest = 1
    
       for i in range(1,len(s)-1):
            for j in range(1,len(s)):
                if i-j < 0 or i+j > len(s)-1:
                    break
                if s[i-j] != s[i+j]:
                    break
            curLen = 2*(j-1) + 1
            if curLen > longest:
                longest = curLen
                res = s[i-j+1:j+i]
    
        for i in range(1,len(s)-2):
            if s[i] != s[i+1]:
                continue
            for j in range(1,len(s)):
                if i-j < 0 or i+1+j > len(s)-1:
                    break
                if s[i-j] != s[i+j+1]:
                    break
            curLen = 2*(j-1) + 2
            if curLen > longest:
                longest = curLen
                res = s[i-j+1:j+i+1]
    
        return res
    

    }


Log in to reply
 

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