Damerau-Levenshtein distance

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

Algorithms

Algorithm	Time complexity	Space complexity
Extension of Wagner-Fischer1	$O(mn)$	$O(mn)$
Space-improved version of Wagner-Fischer1	$O(mn)$	$O(m)$

Footnotes

1. string2string: A Modern Python Library for String-to-String Algorithms ↩ ↩²