Function analiticcl::distance::damerau_levenshtein [−][src]
pub fn damerau_levenshtein(
s: &[CharIndexType],
t: &[CharIndexType],
max_distance: CharIndexType
) -> Option<CharIndexType>
Calculates the Damerau-Levenshtein distance between two strings.
This implementation was adapted from the one in the distance crate by Marcus Brummer (Apache 2 License)
Damerau-Levenshtein distance
The Damerau-Levenshtein distance is the number of per-character changes (insertion, deletion, substitution & transposition) that are neccessary to convert one string into annother. The original Levenshtein distance does not take transposition into account. This implementation does fully support unicode strings.
Complexity
m := len(s) + 2 n := len(t) + 2
Time complexity: O(mn) Space complexity: O(mn + m)