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:
return True
return False
def createKey(self, i, j):
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
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)
Like this:
Like Loading...
Related