Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Calculate edit distance with simple (memoized) recursive algorithm
def distance(s, t, cache=None):
"""Return minimum edit distance between s and t, where an edit
is a character substitution, deletion, or addition.
"""
if not s:
return len(t)
if not t:
return len(s)
if cache is None:
cache = {}
key = (s, t)
if key in cache:
return cache[key]
if s[0] == t[0]:
# First chars equal, return edit distance of the rest
d = distance(s[1:], t[1:], cache)
else:
# First chars not equal, it's 1 + edit distance of the rest
d = 1 + min(
distance(s[1:], t[1:], cache), # substitution of first chars
distance(s[1:], t, cache), # delete first char of s
distance(s, t[1:], cache), # delete first char of t (addition)
)
cache[key] = d
return d
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.