LeetCode 72.编辑距离
题目描述
给定两个单词 word1
和 word2
,计算出将 word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
示例
输入:
word1 = "horse", word2 = "ros"
输出:
3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
算法:动态规划 $O(m*n)$
二维状态表递推解释
$dp[i][j]$ 表示 word1
前 $i$ 个字符转换为 word2
前 $j$ 个字符需要的最短编辑距离
例子
状态表dp
状态表从左往右表示 word1
的字符增多 word2
字符不变
状态表从上往下表示 word2
的字符增多 word1
字符不变
假设表格由 $dp[0][0]$ 开始
横向
$dp[0][1]$ 表示 word1
= b
, word2
= “”,由 word1
变成 word2
的编辑距离(删除字符 b
所以距离为1)
$dp[0][2]$ 表示 word1
= be
, word2
= “”,由 word1
变成 word2
的编辑距离(删除字符 be
所以距离为2)
$dp[0][3]$ 表示 word1
= ben
, word2
= “”,由 word1
变成 word2
的编辑距离(删除字符 ben
所以距离为3)
纵向
$dp[1][0]$ 表示 word1
= “”, word2
= e
,由 word1
变成 word2
的编辑距离(插入字符 e
所以距离为1)
$dp[2][0]$ 表示 word1
= “”, word2
= eb
,由 word1
变成 word2
的编辑距离(插入字符 eb
所以距离为2)
$dp[3][0]$ 表示 word1
= “”, word2
= ebp
,由 word1
变成 word2
的编辑距离(插入字符 ebp
所以距离为3)
$dp[1][1]$ 可以由3个方向得到
-
$dp[0][0] -> dp[1][1]$
word1
=b
,word2
=e
此时将word1
变成word2
的编辑距离 (直接将b
修改为e
, 所以是 $dp[0][0] + 1$ ) -
$dp[0][1] -> dp[1][1]$
word1
=b
,word2
= “”
此时将word1
变成word2
的编辑距离(将b
删除, 所以是$dp[0][1] + 1$) -
$dp[1][0] -> dp[1][1]$
word1
= “” ,word2
=e
此时将word1
变成word2
的编辑距离(增加e
, 所以是$dp[1][0] + 1$) -
如果 $word1[i] == word2[j], 则 dp[i][j] = dp[i - 1][j - 1]$
最后 $dp[i][j]$ 取其中最小值
C++ 代码
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> cost(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i ++ ) {
cost[i][0] = i;
}
for (int i = 1; i <= n; i ++ ) {
cost[0][i] = i;
}
for (int i = 1; i <= m; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
int min_dis = 1e9;
if (word1[i - 1] == word2[j - 1]) {
cost[i][j] = cost[i- 1][j - 1];
} else {
cost[i][j] = 1 + min(min(cost[i - 1][j], cost[i][j - 1]), cost[i - 1][j - 1]);
}
//修改
// min_dis = min(min_dis, cost[i - 1][j - 1] + 1);
//删除
//min_dis = min(min_dis, cost[i][j - 1] + 1);
//增加
// min_dis = min(min_dis, cost[i - 1][j] + 1);
//cost[i][j] = min_dis;
}
}
return cost[m][n];
}
};