DP based solution
class Solution(object):
def __init__(self):
self.lookup = {}
def isPalindrome(self, s, dp, i, k):
j = i + k - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
return True
return False
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
size = len(s)
if size < 2:
return s
dp = [ [False]*size for c in range(size+1) ]
i = j = 0
longest = 0
startIndex = endIndex = 0
while i < size:
dp[i][i] = True
# Handle the case of two repeated chars ('bb')
j = i + 1
if j < size:
if s[i] == s[j]:
dp[i][j] = True
# Always update the index for result.
startIndex = i
endIndex = j
longest = 2
i += 1
# Start finding substrings longer the 2.
k = 3
while k <= size:
for i in range(0, size - k + 1):
if self.isPalindrome(s, dp, i, k):
dp[i][i+k-1] = True
strLen = k
if strLen > longest:
longest = strLen
startIndex = i
endIndex = i + k - 1
k += 1
return s[startIndex: endIndex + 1]
Resources
- https://www.youtube.com/watch?v=UflHuQj6MVA
- https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/
- https://leetcode.com/problems/longest-palindromic-substring/
Written with StackEdit.