传送门: edit-distance
这题是比较简单的 DP 题, 状态 D[i][j] 为子串 word1[..=i] 到 word2[..=j] 的最小编辑距离, 状态转移为
1
| D[i][j] = min(D[i-1][j], D[i][j-1], D[i-1][j-1]) + 1
|
解释一下, 从 D[i][j-1] 到 D[i][j] 相当于插入操作, D[i-1][j] 到 D[i][j] 相当于删除操作, D[i-1][j-1] 到 D[i][j] 就相当于替换操作, 考虑到 i 和 j 位置的字符相同时不需要替换, 所以最后的状态转移为
1
| D[i][j] = min(D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1] + word1[i] != word2[j])
|
然后是我的实现, 加了辅助空串(PS: word1 到 word2 的相互编辑距离是相等的, 所以遍历方向任意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let n = word1.len() + 1;
let m = word2.len() + 1;
let mut d = Vec::new();
d.resize(n * m, 0);
for i in 0..n {
d[i * m] = i as i32;
}
for j in 0..m {
d[j] = j as i32;
}
let word1 = word1.as_bytes();
let word2 = word2.as_bytes();
for i in 1..n {
for j in 1..m {
d[i * m + j] = (d[i * m + j - 1] + 1)
.min(d[(i - 1) * m + j] + 1)
.min(d[(i - 1) * m + j - 1] + (word1[i - 1] != word2[j - 1]) as i32);
}
}
d[n * m - 1]
}
}
|