Advertisement
debetimi

largest palindrome

Aug 15th, 2013
43
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.12 KB | None | 0 0
  1. def largest_palindrone(string):
  2.     if not string:
  3.         return ''
  4.     else:
  5.         longest = ['']
  6.     lp_helper(string, longest)
  7.     return longest
  8.  
  9. def memo(func):
  10.     cache = {}
  11.     cache2 = {}
  12.     def memoize(string, longest):
  13.         if len(longest) == 0:
  14.             key = string
  15.         else:
  16.             key = string + longest[0]
  17.         if not key in cache:
  18.             cache[key] = func(string, longest)
  19.             cache2[key] = longest[0]    
  20.         longest[0] = cache2[key]
  21.         return cache[key]
  22.     return memoize
  23.  
  24. @memo
  25. def lp_helper(string, longest):
  26.     if not string:
  27.         return True
  28.     if len(string) == 1:
  29.         if not len(longest[0]):
  30.             longest[0] = string
  31.         return True
  32.     if string[0] == string[-1]:
  33.         if lp_helper(string[1:len(string)-1], longest):
  34.                 if len(longest[0]) < len(string):
  35.                     longest[0] = string
  36.                 return True
  37.         else:
  38.             return False
  39.     else:
  40.         substr_has_pal = lp_helper(string[1:], longest) or lp_helper(string[0:len(string)-1], longest)
  41.         return False
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement