dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

pub fn levenstein_dist<T: PartialEq>(
    a: &[T],
    b: &[T],
) -> usize {
    let n: usize = a.len();

    let m: usize = b.len();

    let mut dp: Vec<_> = (0..m + 1).collect();

    for i in 0..n {
        let mut ndp = dp.clone();

        ndp[0] = i + 1;

        for j in 0..m {
            ndp[j + 1] = if a[i] == b[j] {
                dp[j]
            } else {
                dp[j].min(dp[j + 1]).min(ndp[j]) + 1
            };
        }

        dp = ndp;
    }

    dp[m]
}