Jabarkan Iteratif dengan matriks dari Jarak Levenshtein

Menghitung jarak Levenshtein yang lebih efisien didasarkan pada pengamatan bahwa jika kita menyimpan matriks untuk mencatat jarak Levenshtein antara semua awalan dari string pertama dan semua awalan pada string kedua, maka kita dapat menghitung nilai-nilai dalam matriks dalam bentuk pemrograman dinamis, sehingga jarak antara dua string penuh sebagai elemen terakhir yang dihitung.

Algoritma ini, contoh dari pemrograman dinamis tipe bottom-up, dibahas dalam artikel 1974 "The String-to-string correction problem" oleh Robert A. Wagner dan Michael J. Fischer. Berikut ini adalah implementasi pseudocode untuk fungsi LevenshteinDistance yang mengambil dua string, s dengan panjang m, dan t dengan panjang n, dan mengembalikan jarak Levenshtein di antara keduanya:function LevenshteinDistance(char s[1..m], char t[1..n]):

// untuk setiap i and j, d[i,j] akan menyimpan jarak Levenshtein distance antara

// i karakter pertama dari s dan j karakter pertama dari t