dsalgo/
levenstein_distance_low_memory_inplace.rs

1pub fn levenstein_dist<T: PartialEq>(
2    a: &[T],
3    b: &[T],
4) -> usize {
5    let n: usize = a.len();
6
7    let m: usize = b.len();
8
9    let mut dp: Vec<_> = (0..m + 1).collect();
10
11    for i in 0..n {
12        for j in (0..m).rev() {
13            dp[j + 1] = if a[i] == b[j] { dp[j] } else { dp[j + 1].min(dp[j]) };
14        }
15
16        dp[0] = i + 1;
17
18        for j in 0..m {
19            if a[i] != b[j] {
20                dp[j + 1] = dp[j + 1].min(dp[j]) + 1;
21            }
22        }
23    }
24
25    dp[m]
26}