编辑距离
解题思路：
-
状态表示：
- f[i][j] 表示将 word1 的前 i 个字符变成 word2 的前 j 个字符所需要进行的最少操作次数；
- 假设 word1 长度为 n，word2 长度为 m，那么 f[n][m] 就表示将 word1 的前 n 个字符变成 word2 的前 m 个字符所需要进行的最少操作次数，即为答案；
-
状态方程：
- word1[i] === word2[j]：当前两个字符相同，不需要做任何操作，此时f[i][j]就可以从f[i - 1][j - 1]的状态转移过来，f[i][j] == f[i - 1][j - 1];
- word1[i] !== word2[j]：
- 替换： 替换word1的第i个字符或者替换word2的第j个字符，则f[i][j] == f[i - 1][j - 1] + 1；
![]( "编辑距离")
- 删除： 删除word1的第i个字符或者删除word2的第j个字符，则f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
![]( "编辑距离")
- 插入: 在 word2[j] 后面添加 word1[i]或者在word1[i]后添加word2[j]，则f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
![]( "编辑距离")
- 替换： 替换word1的第i个字符或者替换word2的第j个字符，则f[i][j] == f[i - 1][j - 1] + 1；
-
状态初始化：将长度为i的word1变成长度为0的word2需要进行最少i次删除操作；将长度为i的word2变成长度为0的word1需要进行最少i次删除操作；
![]( "编辑距离")
复杂度：
-
时间复杂度 ：O(mn)，其中 m 为 word1 的长度，n 为 word2 的长度；
-
空间复杂度 ：O(mn)，需要大小为 O(mn) 的 D 数组来记录状态值；
代码实现：
var minDistance = function (word1, word2) {
let m = word1.length;
let n = word2.length;
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
// 初始化
for (let i = 1; i <= m; i++) dp[i][0] = i;
for (let j = 1; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) { // 最后一位字符一样，不需要任何操作
dp[i][j] = dp[i - 1][j - 1]
} else { // 插入、删除、替换
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
}
}
}
return dp[m][n];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
744.寻找比目标字母大的最小字母
上一篇
评论
