W tablicy o wymiarach przechowywane są odległości między wszystkimi parami prefiksów.
function LevenshteinDistance(s[1..m], t[1..n]): utwórz d[0..m, 0..n]
for i = 0..m: d[i,0] = i
for j = 0..n: d[0,j] = j
for i = 1..m: for j = 1..n: if s[i] = t[j]: koszt = 0 else: koszt = 1
d[i,j] = minimum( d[i-1,j] + 1, // usunięcie s[i] d[i,j-1] + 1, // wstawienie t[j] d[i-1,j-1] + koszt // zgodność albo zamiana )
return d[m,n]
Algorytm wypełniający całą tablicę ma złożoność czasową i pamięciową .
Jeżeli potrzebna jest tylko wartość odległości, wystarczy przechowywać bieżący i poprzedni wiersz (albo kolumnę). Po wybraniu krótszego ciągu jako wymiaru przechowywanego pamięć roboczą można ograniczyć do Esko Ukkonen, „Algorithms for approximate string matching”, Information and Control, t. 64, nr 1–3, 1985, s. 100–118, doi:10.1016/S0019-9958(85)80046-2..
Odtwarzanie operacji Jeżeli zachowana jest pełna tablica, można od komórki przechodzić wstecz do komórek poprzedzających i w ten sposób odtworzyć optymalny ciąg operacji. Dla jednej pary napisów może istnieć więcej niż jedna optymalna sekwencja edycji o tym samym koszcie.