Function distance::damerau_levenshtein

pub fn damerau_levenshtein(s: &str, t: &str) -> usize

Calculates the Damerau-Levenshtein distance between two strings.

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)

Examples

use distance::*;
 
// Damerau-Levenshtein distance
let distance = damerau_levenshtein("hannah", "hannha");   
assert_eq!(1, distance);