# Another Solution: Longest Palindrome Substring

``````class Solution(object):
def __init__(self):
self.lookup = {"test"}

def isPalindrome(self, s, i, k):
j = i + k - 1

if s[i] == s[j]:
key = self.createKey(i + 1, j - 1)
if key in self.lookup:
#self.lookup.remove(key)
return True
return False

def createKey(self, i, j):
#return "{}:{}".format(i,j)
#return (i, j)
#key = bin(i) + bin(j)
#return key
key = i + j/float(10000)
return key

def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
size = len(s)
if size < 2:
return s

i = j = 0
longest = 0
startIndex = endIndex = 0

while i < size:
key = self.createKey(i, i)

j = i + 1
if j < size:
if s[i] == s[j]:
key = self.createKey(i, j)
startIndex = i
endIndex = j
longest = 2
i += 1

k = 3
while k <= size:
for i in range(0, size - k + 1):
if self.isPalindrome(s, i, k):
key = self.createKey(i, i + k - 1)

if k > longest:
longest = k
startIndex = i
endIndex = i + k - 1
k += 1

#print("set length={}".format(len(self.lookup)))
#del self.lookup
result = s[startIndex: endIndex + 1]
return result
``````

## What is Interesting?

• The solution times out
• Python dict or set can’t replace the DP matrix of a 2D lists.
• String `join()` is worse than just `+`
• A tuple is a decent candidate for a hash key
• Integer can create a unique hash key with float operation
`(2,4 => 2.0004) (4,2=> 4.0002)`

This site uses Akismet to reduce spam. Learn how your comment data is processed.