Python


  • 0
    T
    def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            # return self.driver(s, 0, len(s)-1)
            dp = [[0 for i in range(len(s))] for j in range(len(s))]
            
            if len(s) == 0: return None
            if len(s) == 1: return s[0]
            if len(s) == 2: return s if s[0] == s[1] else ""
            
            # initialize base case
            for i in range(len(s)):
                for j in range(len(s)):
                    if i == j: dp[i][j] = 1
            
            # construct matrix
            maxlength = 1
            start = len(s) - 1
            end = len(s) - 1
            for i in range(len(s)-1, -1, -1):
                for j in range(i, len(s)):
                    #if not i == j:
                    if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1] == 1):
                        dp[i][j] = 1
                        if j - i + 1 > maxlength:
                            maxlength = j - i + 1
                            start = i
                            end = j
    
            return s[start:end+1]
    

    Approach 3: Let matrix[i, j] represent whether S_i...S_j inclusive is a substring that is palindrome. With this concept, m[i, i] = 1 because a substring of length 1 is palindromic. Start from the bottom right corner (last element of string) and successively add one more element to the string. i - the outer loop - allows you to add one more element to the string. j - the inner loop - checks where the palindromes lie for the current substring. You can check whether dp[i, j] is 1 or not by checking whether the substring within it is a palindrome (dp[i+1, j-1]). if so, check if the boundary characters are the same. this means that s[i:j+1] (s_i to s_j in python form) is a palindromic substring for the current subproblem. maxlen, start, and end, store the indices of the longest palindromic substring, so by the time i = 0 and j = n-1 start and end will hold the longest palindromic substring.


Log in to reply
 

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