algorithms_edu/problems/dp/
edit_distance.rs

1use std::cmp::min;
2
3#[allow(clippy::needless_range_loop)]
4pub fn edit_distance(s1: &[u8], s2: &[u8]) -> u32 {
5    let (m, n) = (s1.len(), s2.len());
6    let mut dp_matrix = vec![vec![0u32; n + 1]; m + 1];
7    for j in 1..=n {
8        dp_matrix[0][j] = j as u32;
9    }
10    for i in 1..=m {
11        dp_matrix[i][0] = i as u32;
12    }
13    for i in 1..=m {
14        for j in 1..=n {
15            let diag = dp_matrix[i - 1][j - 1] + if s1[i - 1] == s2[j - 1] { 0 } else { 1 };
16            let up = dp_matrix[i - 1][j] + 1;
17            let left = dp_matrix[i][j - 1] + 1;
18            dp_matrix[i][j] = min(diag, min(up, left));
19        }
20    }
21    dp_matrix[m][n]
22}
23
24pub fn edit_distance_space_efficient(s1: &[u8], s2: &[u8]) -> u32 {
25    let (m, n) = (s1.len(), s2.len());
26    let mut dp_matrix: Vec<u32> = Vec::with_capacity(n + 1); // the dynamic programming matrix (only 1 column stored)
27    let mut s_diag: u32; // dp_matrix[i - 1][j - 1]
28    let mut s_left: u32; // dp_matrix[i][j - 1]
29    let mut a: u8; // s1[i - 1]
30    let mut b: u8; // s2[j - 1]
31
32    // 0th row
33    for j in 0..=(n as u32) {
34        dp_matrix.push(j);
35    }
36    // rows 1 to m
37    for i in 1..=m {
38        s_diag = (i - 1) as u32;
39        s_left = i as u32;
40        a = s1[i - 1];
41        for j in 1..=n {
42            b = s2[j - 1];
43            s_left = min(
44                s_diag + if a == b { 0 } else { 1 },
45                min(s_left + 1, dp_matrix[j] + 1),
46            );
47            s_diag = dp_matrix[j];
48            dp_matrix[j] = s_left;
49        }
50    }
51
52    dp_matrix[n]
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58    #[test]
59    fn test_edit_distance() {
60        let a = b"banana";
61        let b = b"Canada";
62        assert_eq!(edit_distance(a, b), 2);
63        assert_eq!(edit_distance_space_efficient(a, b), 2);
64        let a = b"Mississippi";
65        let b = b"ssi";
66        assert_eq!(edit_distance(a, b), 8);
67        assert_eq!(edit_distance_space_efficient(a, b), 8);
68    }
69}
algorithms_edu/problems/dp/edit_distance.rs

algorithms_edu/problems/dp/
edit_distance.rs
