harness_write/
levenshtein.rs

1/// Levenshtein distance O(n*m) time, O(min(n,m)) space.
2pub fn levenshtein(a: &str, b: &str) -> usize {
3    if a == b {
4        return 0;
5    }
6    if a.is_empty() {
7        return b.chars().count();
8    }
9    if b.is_empty() {
10        return a.chars().count();
11    }
12    let a_chars: Vec<char> = a.chars().collect();
13    let b_chars: Vec<char> = b.chars().collect();
14    let (s1, s2) = if a_chars.len() < b_chars.len() {
15        (b_chars, a_chars)
16    } else {
17        (a_chars, b_chars)
18    };
19    let m = s1.len();
20    let n = s2.len();
21    let mut prev: Vec<usize> = (0..=n).collect();
22    let mut curr: Vec<usize> = vec![0; n + 1];
23    for i in 1..=m {
24        curr[0] = i;
25        let si = s1[i - 1];
26        for j in 1..=n {
27            let cost = if si == s2[j - 1] { 0 } else { 1 };
28            let del = prev[j] + 1;
29            let ins = curr[j - 1] + 1;
30            let sub = prev[j - 1] + cost;
31            curr[j] = del.min(ins).min(sub);
32        }
33        prev.copy_from_slice(&curr);
34    }
35    prev[n]
36}
37
38pub fn similarity(a: &str, b: &str) -> f64 {
39    let max_len = a.chars().count().max(b.chars().count());
40    if max_len == 0 {
41        return 1.0;
42    }
43    1.0 - (levenshtein(a, b) as f64 / max_len as f64)
44}
harness_write/levenshtein.rs

harness_write/
levenshtein.rs
