Function distance::levenshtein

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

Calculates the Levenshtein distance between two strings.

Levenshtein distance

The Levenshtein distance is the number of per-character changes (insertion, deletion & substitution) that are neccessary to convert one string into annother. This implementation does fully support unicode strings.

Complexity

m := len(s) + 1
n := len(t) + 1

Time complexity: O(mn)
Space complexity: O(mn)

Examples

use distance::*;
 
// Levenshtein distance
let distance = levenshtein("hannah", "hanna");   
assert_eq!(1, distance);