memoization_example.py

class memorize(dict):
    def __init__(self, func):
        self.func = func

    def __call__(self, *args):
        return self[args]

    def __missing__(self, key):
        self[key] = self.func(*key)
        return self[key]


@memorize
def deletion_distance(str1, str2):
  if not str1:
    return len(str2)
  
  if not str2:
    return len(str1)
  
  if str1[0] == str2[0]:
    return deletion_distance(str1[1:], str2[1:])
    
  return min(
    1 + deletion_distance(str1[1:], str2),
    1 + deletion_distance(str1, str2[1:])
  )


memo = {}
def deletion_distance_with_memo(str1, str2):
  key = (str1, str2)
  if key in memo:
    return memo[key]
  
  if not str1:
    memo[key] = len(str2)  
  elif not str2:
    memo[key] = len(str1)
  elif str1[0] == str2[0]:
    memo[key] = deletion_distance(str1[1:], str2[1:])
  else:
    memo[key] = min(
      1 + deletion_distance(str1[1:], str2),
      1 + deletion_distance(str1, str2[1:])
    )
  return memo[key]