My O(N^2) python solution - 1500ms


  • 0
    S
    class Solution:
        # @param {string} s
        # @return {string}
        def longestPalindrome(self, s):
            longest = (1, (0, 0))
            for i in xrange(len(s)):
                # expand i, i - expand around center; expand i, i+1 expand around a pair
                longest = max(longest, self.expand(i, i, s), self.expand(i, i+1, s), key=lambda x: x[0])
    
            return s[longest[1][0]:longest[1][1]+1]
    
        def expand(self, start, end, s):
            # expand around center
            while start >= 0 and end < len(s):
                if s[start] == s[end]:
                    start -= 1
                    end += 1
                else: break
    
            # Rollback one
            start += 1
            end -= 1
            return (end - start + 1, (start, end))

Log in to reply
 

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