Levenshtein distance

Type of Edit distance, which takes into account only insert, delete and substitute operations.

dist_{Lev}(a,b) = \begin{cases} |a|,& \text{if } |b| = 0\\ |b|,& \text{if } |a| = 0\\ dist_{Lev}(tail(a), tail(b)),& \text{if } head(a) = head(b)\\ 1 + min \begin{cases} dist_{Lev}(tail(a), b) \\ dist_{Lev}(a, tail(b)) \\ dist_{Lev}(tail(a), tail(b)) \end{cases} & \text{otherwise} \end{cases}

Weighted Levenshtein distance

Another variation is to add weight (or score) to edit operations:

We can modify wiegth of delete and insert, but they need to be the same to preserve symmetry property
We can modify weight of substitution, but it makes sense to choose values less than to 2 times weight of insert/delete. Otherwise algorithm can as well count it as 1 deletion, 1 insertion.

The more chances of replacing one letter with another, the less weight, for example:

Algorithm	Time complexity	Space complexity
Wagner-Fischer¹	$O(mn)$	$O(mn)$
Space-improved version of Wagner-Fischer²	$O(mn)$	$O(m)$
Masek-Paterson³	$O(n \max( 1, m/\log(n)))$

Dynamic programming solution aka Wagner-Fischer:
- algorithm-visualizer
- observablehq

Algorithm	Time complexity	Space complexity
Andoni-Nosatzki: ⁴	$O(n^{1+\epsilon}), \epsilon>0$
Ukkonen ⁵	$O(n + d^2)$
Myers ⁶ ⁷	$O(n + d^2)$	$O(n)$
BJK ⁸	$O(n^{3/7})$