lev/
lib.rs

1#![doc = include_str!("../README.md")]
2
3/// Returns the [Levenshtein distance][1] between `a` and `b`.
4///
5/// [1]: https://en.wikipedia.org/wiki/Levenshtein_distance#Definition
6pub fn lev<T: PartialEq>(
7    a: impl Clone + Iterator<Item = T>,
8    b: impl Clone + Iterator<Item = T>,
9) -> usize {
10    let (mut tail_a, mut tail_b) = (a.clone(), b.clone());
11    let Some(x) = tail_a.next() else {
12        return b.count();
13    };
14    let Some(y) = tail_b.next() else {
15        return a.count();
16    };
17    if x == y {
18        lev(tail_a, tail_b)
19    } else {
20        1 + lev(tail_a.clone(), b)
21            .min(lev(a, tail_b.clone()))
22            .min(lev(tail_a, tail_b))
23    }
24}
25
26#[cfg(test)]
27mod tests {
28    use super::*;
29
30    #[test]
31    fn lev_works_on_wikipedia_examples() {
32        for (a, b, n) in [
33            ("kitten", "sitting", 3),       // sub, sub, insert
34            ("uninformed", "uniformed", 1), // delete
35        ] {
36            assert_eq!(lev(a.bytes(), b.bytes()), n);
37            assert_eq!(lev(a.chars(), b.chars()), n);
38        }
39    }
40}
lev/lib.rs

lev/
lib.rs
