| 1 | pub(crate) fn distance(a: &str, b: &str) -> usize { |
| 2 | if a == b { |
| 3 | return 0; |
| 4 | } |
| 5 | match (a.chars().count(), b.chars().count()) { |
| 6 | (0, b) => return b, |
| 7 | (a, 0) => return a, |
| 8 | // (a_len, b_len) if a_len < b_len => return distance(b, a), |
| 9 | _ => (), |
| 10 | } |
| 11 | |
| 12 | let mut result = 0; |
| 13 | let mut cache: Vec<usize> = (1..a.chars().count() + 1).collect(); |
| 14 | |
| 15 | for (index_b, char_b) in b.chars().enumerate() { |
| 16 | result = index_b; |
| 17 | let mut distance_a = index_b; |
| 18 | |
| 19 | for (index_a, char_a) in a.chars().enumerate() { |
| 20 | let distance_b = if char_a == char_b { |
| 21 | distance_a |
| 22 | } else { |
| 23 | distance_a + 1 |
| 24 | }; |
| 25 | |
| 26 | distance_a = cache[index_a]; |
| 27 | |
| 28 | result = if distance_a > result { |
| 29 | if distance_b > result { |
| 30 | result + 1 |
| 31 | } else { |
| 32 | distance_b |
| 33 | } |
| 34 | } else if distance_b > distance_a { |
| 35 | distance_a + 1 |
| 36 | } else { |
| 37 | distance_b |
| 38 | }; |
| 39 | |
| 40 | cache[index_a] = result; |
| 41 | } |
| 42 | } |
| 43 | result |
| 44 | } |