0072.编辑距离
难度：🟡 中等
标签：字符串、动态规划
链接：72. 编辑距离
题目描述
给你两个单词 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')
解题思路
核心思想
本题是动态规划领域的里程碑式问题，旨在计算两个字符串之间的编辑距离 (Edit Distance)。核心思想是通过解决子问题——即计算两个字符串前缀之间的编辑距离——来逐步构建出整个问题的解。
思路选择
动态规划 (Dynamic Programming) 是解决此问题的标准最优思路。
我们可以定义一个二维
dp表，其中dp[i][j]表示将word1的前i个字符（word1[0...i-1]）转换为word2的前j个字符（word2[0...j-1]）所需的最少操作数。状态转移 的逻辑如下：
如果
word1[i-1]与word2[j-1]相等，说明最后一个字符无需操作，问题退化为计算word1前i-1个字符与word2前j-1个字符的编辑距离。即dp[i][j] = dp[i-1][j-1]。如果
word1[i-1]与word2[j-1]不相等，我们需要在三种操作中选择成本最低的一种：替换：将
word1[i-1]替换为word2[j-1]。成本为dp[i-1][j-1] + 1。删除：删除
word1的第i个字符。成本为dp[i-1][j] + 1。插入：在
word1的第i个字符后插入一个字符。成本为dp[i][j-1] + 1。 我们取这三者中的最小值，即dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。
关键步骤
初始化：创建一个
(m+1) x (n+1)的dp数组，其中m和n分别是word1和word2的长度。设置边界条件：
dp[i][0] = i：将长度为i的word1转换为长度为 0 的word2，需要i次删除操作。dp[0][j] = j：将长度为 0 的word1转换为长度为j的word2，需要j次插入操作。
双层循环：遍历
dp表，从dp[1][1]开始，根据上述状态转移方程填充每个dp[i][j]。返回结果：遍历结束后，
dp[m][n]的值就是word1和word2之间的最小编辑距离。
代码实现
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function (word1, word2) {
const m = word1.length;
const n = word2.length;
// dp[i][j] 表示 word1 的前 i 个字符到 word2 的前 j 个字符的编辑距离
const dp = new Array(m + 1).fill(null).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;
}
// 填充 dp 表
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 {
// 字符不同，取三种操作的最小值 + 1
dp[i][j] = Math.min(
dp[i - 1][j], // 删除
dp[i][j - 1], // 插入
dp[i - 1][j - 1] // 替换
) + 1;
}
}
}
return dp[m][n];
};
复杂度分析
时间复杂度：O(m × n) 其中 m 和 n 分别是两个字符串的长度。我们需要填充整个
dp表。空间复杂度：O(m × n) 我们需要一个二维数组来存储
dp表。可以通过状态压缩将空间复杂度优化到 O(min(m, n))。
相关题目
总结
本题是动态规划中关于字符串编辑问题的奠基之作，其状态转移方程深刻地体现了 DP “最优子结构”和“无后效性”的特点。理解插入、删除、替换三种操作如何对应到 dp 表中相邻三个格子的状态，是掌握此算法的关键。