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)
self.lookup.add(key)
j = i + 1
if j < size:
if s[i] == s[j]:
key = self.createKey(i, j)
self.lookup.add(key)
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)
self.lookup.add(key)
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)
