Longest Palindromic Substring – Python 3 (Week 13 – 06)

class Solution:
    """
    @param s: input string
    @return: the longest palindromic substring
    """
    def longestPalindrome(self, s):
        # write your code here
        if not s:
            return ''
        longest = ''
        for mid in range(len(s)):
            sub = self.find_palindrome_from(s, mid, mid)
            if len(sub) > len(longest):
                longest = sub
            
            sub = self.find_palindrome_from(s, mid, mid + 1)
            if len(sub) > len(longest):
                longest = sub
            
        return longest
           
          
           
           
           
    def find_palindrome_from(self, string, left, right):
        while left >= 0 and right < len(string) and string[left] == string[right]:
            left -= 1
            right += 1
        return string[left + 1 : right]    

 class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
            
        n = len(s)
        is_palindrome = [[False] * n for _ in range(n)]
        
        for i in range(n):
            is_palindrome[i][i] = True
        for i in range(1, n):
            is_palindrome[i][i - 1] = True
            
        longest, start, end = 1, 0, 0           
        for length in range(1, n):
            for i in range(n - length):
                j = i + length
                #if s[i] == s[j] and is_palindrome[i + 1][j - 1]:
                #    is_palindrome[i][j] = True
                is_palindrome[i][j] = s[i] == s[j] and is_palindrome[i + 1][j - 1]
                if is_palindrome[i][j] and length + 1 > longest:
                    longest = length + 1
                    start, end = i, j
        return s[start : end + 1]