blob: 98caa20e96ee96059427d0f608a0b7a81c61f433 (
plain)
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
|
use std::cmp::min;
pub fn levenshtein_distance(a: &str, b: &str) -> usize {
let a_len = a.chars().count();
let b_len = b.chars().count();
if a_len == 0 {
return b_len;
}
if b_len == 0 {
return a_len;
}
let mut prev_row: Vec<usize> = (0..=b_len).collect();
let mut curr_row = vec![0; b_len + 1];
let mut a_chars = a.chars();
for i in 1..=a_len {
let a_char = a_chars.next().unwrap();
curr_row[0] = i;
let mut b_chars = b.chars();
for j in 1..=b_len {
let b_char = b_chars.next().unwrap();
let cost = if a_char == b_char { 0 } else { 1 };
curr_row[j] = min(
prev_row[j] + 1,
min(curr_row[j - 1] + 1, prev_row[j - 1] + cost),
);
}
std::mem::swap(&mut prev_row, &mut curr_row);
}
prev_row[b_len]
}
|
