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 if len(s) == 2: return s if s == s 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.