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)`
Vishal

A voyager on the journey to technology and art of software development. Pursuing arts, music, photography, and ways to live life on the edge

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