longest palindrome

lp.py

#!/usr/bin/env python3

def lp(x, i=None, j=None, cache={}):
	if i is None or j is None:
		i = 0
		j = len(x)-1

	if (i, j) in cache.keys():
		return cache[(i, j)]

	if i > j:
		return 0
	if i == j:
		return 1
	if x[i] == x[j]:
		result = 2 + lp(x, i+1, j-1, cache=cache)
		cache[(i, j)] = result
		return result
	else:
		result = max(
			lp(x, i, j-1, cache=cache),
			lp(x, i+1, j, cache=cache)
		)
		cache[(i, j)] = result
		return result


def slow_lp(x, i=None, j=None):
	if i is None or j is None:
		i = 0
		j = len(x)-1

	if i > j:
		return 0
	if i == j:
		return 1
	if x[i] == x[j]:
		return 2 + lp(x, i+1, j-1)
	else:
		return max(
			lp(x, i, j-1),
			lp(x, i+1, j)
		)

if __name__ == "__main__":
	import timeit
	s = """from __main__ import slow_lp, lp
import string, random
text = ''.join(random.choice(string.ascii_uppercase) for _ in range(250))"""

	regular = timeit.Timer("slow_lp(text)", setup=s)
	print("Regular: {}".format(min(regular.repeat())))

	memoized = timeit.Timer("lp(text)", setup=s)
	print("Memoized: {}".format(min(memoized.repeat())))