Η απόσταση Levenshtein είναι μια μετρική η οποία μετράει την διαφορά μεταξύ δύο συμβολοσειρών.
Ορίζεται ως ο ελάχιστος αριθμός αλλαγών χαρακτήρων (εισαγωγές, διαγραφές ή αλλαγές) που απαιτούνται
προκειμένου να μετατρέψουμε μια συμβολοσειρά σε μια άλλη και προέρχεται από τον Ρώσο μαθηματικό
Vladimir Levenshtein.
Η απόσταση Levenshtein μεταξύ δύο συμβολοσειρών a,b, δίνεται από την σχέση:
https://en.wikipedia.org/wiki/Levenshtein_distance
Για παράδειγμα η απόσταση Levenshtein μεταξύ των λέξεων kitten και sitting είναι 3.
1. kitten -> sitten (αλλαγή)
2. sitten -> sittin (αλλαγή)
3. sittin -> sitting (πρόσθεση)

Ακολουθεί ψευδοκώδικας για την υλοποίηση της συνάρτησης Levenshtein Distance

function LevenshteinDistance(char s[1..m], char t[1..n]):
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t
declare int d[0..m, 0..n]

set each element in d to zero

// source prefixes can be transformed into empty string by
// dropping all characters
for i from 1 to m:
d[i, 0] := i

// target prefixes can be reached from empty source prefix
// by inserting every character
for j from 1 to n:
d[0, j] := j

for j from 1 to n:
for i from 1 to m:
if s[i] = t[j]:
substitutionCost := 0
else:
substitutionCost := 1

d[i, j] := minimum(d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + substitutionCost) // substitution

return d[m, n]