utils/src/levenshtein_distance.rs


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
29
30
31
32
33
34

use std::cmp::min;

pub fn levenshtein_distance(a: &str, b: &str) -> usize {
    let a_chars: Vec<char> = a.chars().collect();
    let b_chars: Vec<char> = b.chars().collect();
    let a_len = a_chars.len();
    let b_len = b_chars.len();

    if a_len == 0 {
        return b_len;
    }
    if b_len == 0 {
        return a_len;
    }

    let mut dp = vec![vec![0; b_len + 1]; a_len + 1];

    for (i, row) in dp.iter_mut().enumerate() {
        row[0] = i;
    }

    for (j, cell) in dp[0].iter_mut().enumerate() {
        *cell = j;
    }

    for (i, a_char) in a_chars.iter().enumerate() {
        for (j, b_char) in b_chars.iter().enumerate() {
            let cost = if a_char == b_char { 0 } else { 1 };
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, min(dp[i + 1][j] + 1, dp[i][j] + cost));
        }
    }

    dp[a_len][b_len]
}