Der DP-Algorithmus zur Berechnung der Levenshtein-Distanz ist mit dem Needleman-Wunsch-Algorithmus zur Berechnung des Sequenzalignments zweier Zeichenketten verwandt. Der Needleman-Wunsch-Algorithmus ist in  und lässt beliebige Kostenfunktionen für Einfüge- bzw. Löschoperationen der Länge  zu. Bei dem Levenshtein-Algorithmus besteht eine Einfüge- bzw. Löschoperation aus maximal einem Zeichen. Varianten des Needleman-Wunsch Algorithmus beschränken die Wahl der Kostenfunktion, so dass deren Laufzeit in  liegt.