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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
use std::cmp::min;
#[allow(clippy::needless_range_loop)]
pub fn edit_distance(s1: &[u8], s2: &[u8]) -> u32 {
let (m, n) = (s1.len(), s2.len());
let mut dp_matrix = vec![vec![0u32; n + 1]; m + 1];
for j in 1..=n {
dp_matrix[0][j] = j as u32;
}
for i in 1..=m {
dp_matrix[i][0] = i as u32;
}
for i in 1..=m {
for j in 1..=n {
let diag = dp_matrix[i - 1][j - 1] + if s1[i - 1] == s2[j - 1] { 0 } else { 1 };
let up = dp_matrix[i - 1][j] + 1;
let left = dp_matrix[i][j - 1] + 1;
dp_matrix[i][j] = min(diag, min(up, left));
}
}
dp_matrix[m][n]
}
pub fn edit_distance_space_efficient(s1: &[u8], s2: &[u8]) -> u32 {
let (m, n) = (s1.len(), s2.len());
let mut dp_matrix: Vec<u32> = Vec::with_capacity(n + 1);
let mut s_diag: u32;
let mut s_left: u32;
let mut a: u8;
let mut b: u8;
for j in 0..=(n as u32) {
dp_matrix.push(j);
}
for i in 1..=m {
s_diag = (i - 1) as u32;
s_left = i as u32;
a = s1[i - 1];
for j in 1..=n {
b = s2[j - 1];
s_left = min(
s_diag + if a == b { 0 } else { 1 },
min(s_left + 1, dp_matrix[j] + 1),
);
s_diag = dp_matrix[j];
dp_matrix[j] = s_left;
}
}
dp_matrix[n]
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_edit_distance() {
let a = b"banana";
let b = b"Canada";
assert_eq!(edit_distance(a, b), 2);
assert_eq!(edit_distance_space_efficient(a, b), 2);
let a = b"Mississippi";
let b = b"ssi";
assert_eq!(edit_distance(a, b), 8);
assert_eq!(edit_distance_space_efficient(a, b), 8);
}
}