Advertisement
avisrivastava254084

Untitled

Sep 22nd, 2019
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.35 KB | None | 0 0
  1. memoized = {}
  2. curr_length = 0
  3. curr_pal = ""
  4.  
  5.  
  6. class Solution:
  7.     def check_palindrome(self, str_):
  8.         if len(str_) <= 1:
  9.             return False
  10.         global curr_length
  11.         if len(str_) <= curr_length:
  12.             return False
  13.         if memoized.get(str_, None):
  14.             return memoized[str_]
  15.         if str_ == str_[::-1]:
  16.             memoized[str_] = True
  17.             curr_length = len(str_)
  18.             return True
  19.         memoized[str_] = False
  20.         return False
  21.  
  22.     def longest_palindrome(self, str_):
  23.         if len(str_) <= 1:
  24.             return None
  25.         n = len(str_)
  26.         global curr_length
  27.         if n <= curr_length:
  28.             memoized[str_] = False
  29.             return None
  30.         if self.check_palindrome(str_):
  31.             return str_
  32.         n -= 1
  33.         return(self.longest_palindrome(str_[:n]))
  34.  
  35.     def longestPalindrome(self, s):
  36.         global curr_length
  37.         global curr_pal
  38.         for starting_index in range(len(s)):
  39.             pal = self.longest_palindrome(s[starting_index:])
  40.             if pal:
  41.                 if len(pal) > len(curr_pal):
  42.                     curr_pal = pal
  43.                     curr_length = len(curr_pal)
  44.         return curr_pal
  45.  
  46.  
  47.  
  48. solution = Solution()
  49. # print(solution.longestPalindrome("babadda"))
  50. print(solution.longestPalindrome("cbbd"))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement