原题地址：编辑距离
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
动态规划
用一个二维数组$dp$来记录word1和word2中各子串的编辑距离，$dp[i][j]$表示word1前$i$个字符到word2前$j$个字符的编辑距离。
具体实现方法如下：
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
const minDistance1 = function(word1, word2) {
let [m, n] = [word1.length, word2.length];
// word1或word2中有一个为空串时，最短编辑距离为另一个串的长度
if (m === 0) {
return n;
}
if (n === 0) {
return m;
}
// 用一个二维数组来记录编辑距离
// dp[i][j]表示word1前i个字符到word2前j个字符的编辑距离
// 注意dp的长度为(m+1)*(n+1)
let dp = new Array(m + 1);
for (let i = 0; i <= m; i ++) {
dp[i] = new Array(n + 1).fill(0);
}
for (let i = 0; i <= m; i ++) {
for (let j = 0; j <= n; j ++) {
if (i === 0) {
// 原串为空时，加入目标串的所有字符即可
dp[i][j] = j;
} else if ( j === 0) {
// 目标串为空时，删除原串的所有字符即可
dp[i][j] = i;
} else {
if (word1[i - 1] === word2[j - 1]) {
// 如果两边最后一个字符相等，就不用处理，编辑距离与前面部分的相同
dp[i][j] = dp[i - 1][j - 1]
} else {
// 有替换、插入、删除三种操作可以选择，找出其中编辑距离最小的一个
let replaceDistance = dp[i - 1][j - 1] + 1;
let insertDistance = dp[i][j - 1] + 1;
let deleteDistance = dp[i - 1][j] + 1;
dp[i][j] = Math.min(replaceDistance, Math.min(insertDistance, deleteDistance));
}
}
}
}
// 返回word1到word2的编辑距离
return dp[m][n];
};
测试：
let start = new Date();
const test = minDistance1;
console.log(test("intention", "execution")); // 5
console.log(test("horse", "ros")); // 3
console.log(new Date().getTime() - start.getTime()); // 16
时间复杂度： 双重遍历，时间复杂度为$O((M+1)(N+1))$
空间复杂度： 空间复杂度为$O((M+1)(N+1))$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 24,2019