Szathmáry László honlapja @ DEIK | Nim2 / Levenshtein distance

See also std/editdistance

"The Levenshtein distance is a string metric for measuring the difference between two sequences. The Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after Soviet mathematician Vladimir Levenshtein, who defined the metric in 1965." source

_{"Levenstein" is a common misspelling that omits the "h."}

Levenshtein

def LD(s: str, t: str) -> int:
"""Levenshtein distance"""
s = " " + s
t = " " + t
d = {}
S = len(s)
T = len(t)
for i in range(S):
d[i, 0] = i
for j in range(T):
d[0, j] = j
for j in range(1, T):
for i in range(1, S):
if s[i] == t[j]:
d[i, j] = d[i - 1, j - 1]
else:
d[i, j] = min(d[i - 1, j] + 1, d[i, j - 1] + 1, d[i - 1, j - 1] + 1)
return d[S - 1, T - 1]

print(LD("quickjump", "qjump")) # 4 ; four deletions

import std/editdistance

echo editDistance("quickjump", "qjump")
# 4 ; four deletions