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

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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