Misc

levenshtein_recursive.rs

pub fn levenshtein_distance(a: &str, b: &str) -> usize {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    
    levenshtein_distance_inner(&a, &b)
}

fn levenshtein_distance_inner(a: &[char], b: &[char]) -> usize {
    if a.len() == 0 {
        return b.len();
    }
    
    if b.len() == 0 {
        return a.len();
    }
    
    let cost = if b.get(b.len() - 1) == a.get(a.len() - 1) { 0 } 
               else { 1 };
     
    let cases = [
        levenshtein_distance_inner(a, &b[..b.len() - 1]) + 1,
        levenshtein_distance_inner(&a[..a.len() - 1], b) + 1,
        levenshtein_distance_inner(&a[..a.len() - 1], &b[..b.len() - 1]) + cost,
    ];
    
    *cases.iter().min().unwrap()
}

#[test]
fn tests() {
    let comp = |a, b, v| assert_eq!(levenshtein_distance(a, b), v);
    
    comp("abc", "abc", 0);
    
    comp("abc", "abd", 1);
    comp("abc", "acd", 2);
    comp("abc", "xyz", 3);
    
    comp("abc", "abcd", 1);
    comp("abc", "abcde", 2);
    comp("abc", "abcdef", 3);
    
    comp("abc", "ab", 1);
    comp("abc", "a", 2);
    comp("abc", "", 3);
}