1. 问题
给定2个字符串word1, word2。可以插入、删除、替换一个字符让word1变成word2，每次操作计1次，求最小操作次数。
2. 解答思路
经典的动态规划题，需要重点标记！！
令dp(i, j)为单词s[:i]与t[:j]的编辑距离。
我们只看最后一个字符，根据三种操作，有：
- 最后一个字符是要被删除的：不论匹配与否，
dp(i, j) = 1 + dp(i, j-1)- 我们得到
s[:i]与t[:j-1]的编辑距离，然后把t[j]给删除
- 我们得到
- 最后一个字符是要被插入的：不论匹配与否，
dp(i, j) = 1 + dp(i-1, j)- 我们得到
s[:i-1]与t[:j]的编辑距离，然后给t末尾插入s[i]
- 我们得到
- 最后一个字符是要被更改的：
- 若匹配，即
s[i] == t[j]：很明显，dp(i,j) = dp(i-1, j-1) - 若不匹配：则需要更改最后一个字符，
dp(i, j) = 1 + dp(i-1, j-1)
- 若匹配，即
递归的时候，只需取三个操作的最小值即可。
此外，基础值dp(0,j) = j，dp(i, 0) = i。
3. 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
use std::cmp::min;
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let word1 = Vec::from(word1);
let word2 = Vec::from(word2);
let mut dp = vec![vec![0; word2.len() + 1]; word1.len() + 1];
for i in 0..dp.len() {
dp[i][0] = i as i32;
}
for i in 0..dp[0].len() {
dp[0][i] = i as i32;
}
for i in 1..dp.len() {
for j in 1..dp[i].len() {
let del_dist = dp[i][j - 1] + 1;
let insert_dist = dp[i - 1][j] + 1;
let mod_dist = if word1[i - 1] == word2[j - 1] {
dp[i - 1][j - 1]
} else {
dp[i - 1][j - 1] + 1
};
dp[i][j] = min(del_dist, min(insert_dist, mod_dist));
}
}
return dp[word1.len()][word2.len()];
}
}
4. 相似题目
-
Problem 583：https://leetcode-cn.com/problems/delete-operation-for-two-strings/
在上文提及的题目相比，只考虑删除操作
-
Problem 712：https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/
在583题目基础上，将次数修改为删除的字符ASCII值的和
