| 3 | use std::cmp::min; |
| 4 | |
| 5 | fn edit_distance(source: &str, target: &str) -> usize { |
| 6 | // 极端情况：空字符串到字符串的转换 |
| 7 | if source.is_empty() { |
| 8 | return target.len(); |
| 9 | } else if target.is_empty() { |
| 10 | return source.len(); |
| 11 | } |
| 12 | |
| 13 | // 建立矩阵存储过程值 |
| 14 | let source_c = source.chars().count(); |
| 15 | let target_c = target.chars().count(); |
| 16 | let mut distance = vec![vec![0;target_c+1]; source_c+1]; |
| 17 | (1..=source_c).for_each(|i| { |
| 18 | distance[i][0] = i |
| 19 | }); |
| 20 | (1..=target_c).for_each(|j| { |
| 21 | distance[0][j] = j |
| 22 | }); |
| 23 | |
| 24 | // 存储过程值，取增、删、改中的最小步骤数 |
| 25 | for (i, cs) in source.chars().enumerate() { |
| 26 | for (j, ct) in target.chars().enumerate() { |
| 27 | let ins = distance[i+1][j] + 1; |
| 28 | let del = distance[i][j+1] + 1; |
| 29 | let sub = distance[i][j] + (cs != ct) as usize; |
| 30 | distance[i+1][j+1] = min(min(ins, del), sub); |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | // 返回最后一行最后一列的值 |
| 35 | *distance.last().and_then(|d| d.last()).unwrap() |
| 36 | } |
| 37 | |
| 38 | // 优化版，使用一个 Vec 来存储过程值 |
| 39 | fn edit_distance2(source: &str, target: &str) -> usize { |