competitive/combinatorial_optimization/
levenshtein_distance.rs

1pub fn levenshtein_distance<T: PartialEq>(x: &[T], y: &[T]) -> usize {
2    let n = x.len();
3    let m = y.len();
4    let mut dp = vec![vec![0; m + 1]; n + 1];
5    for (i, dp) in dp.iter_mut().enumerate() {
6        dp[0] = i;
7    }
8    for j in 1..=m {
9        dp[0][j] = j;
10    }
11    for (i, x) in x.iter().enumerate() {
12        for (j, y) in y.iter().enumerate() {
13            dp[i + 1][j + 1] =
14                (dp[i][j + 1].min(dp[i + 1][j]) + 1).min(dp[i][j] + (x != y) as usize);
15        }
16    }
17    dp[n][m]
18}