Datenstrukturdienstag:
In Anlehnung an letzte Woche: Die Levensthein-Distanz.

Ein Maß für die Ähnlichkeit zweiter Strings. Grob gesagt gibt es an, wie viele Tasten man auf der Tastatur drücken muss, um von einem String auf den anderen zu kommen (mit Backspace etc).
Es gibt verschiedene Algorithmen, um dieses Maß zu berechnen. Auf Wikipedia ist eine rekursive und eine Matrix-Variante. Sie unterscheiden sich deutlich in der Platzkomplexität.

Verwenden kann man das z. B: für eine Rechtschreibkorrektur. Oder generell, wenn man Nutzereingaben hat und man weiß, dass Nutzer sich genre vertippen.