优化版，使用一个 Vec 来存储过程值
(source: &str, target: &str)
| 37 | |
| 38 | // 优化版，使用一个 Vec 来存储过程值 |
| 39 | fn edit_distance2(source: &str, target: &str) -> usize { |
| 40 | // 极端情况：空字符串到字符串的转换 |
| 41 | if source.is_empty() { |
| 42 | return target.len(); |
| 43 | } else if target.is_empty() { |
| 44 | return source.len(); |
| 45 | } |
| 46 | |
| 47 | // distances 存储了到各种字符串的编辑距离 |
| 48 | let target_c = target.chars().count(); |
| 49 | let mut distances = (0..=target_c).collect::<Vec<_>>(); |
| 50 | for (i, cs) in source.chars().enumerate() { |
| 51 | let mut substt = i; |
| 52 | distances[0] = substt + 1; |
| 53 | |
| 54 | // 不断组合计算各个距离 |
| 55 | for (j, ct) in target.chars().enumerate() { |
| 56 | let dist = min(min(distances[j], distances[j+1])+1, |
| 57 | substt + (cs != ct) as usize); |
| 58 | substt = distances[j+1]; |
| 59 | distances[j+1] = dist; |
| 60 | } |
| 61 | } |
| 62 | |
| 63 | // 最后一个距离值就是最终答案 |
| 64 | distances.pop().unwrap() |
| 65 | } |
| 66 | |
| 67 | fn main() { |
| 68 | let source = "abce"; |