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