.jpg)
955 字
5 分钟
编辑距离
题目描述
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
解题思路
- 定义状态：
- 创建二维数组
dp[i][j]，表示将word1的前i个字符转换为word2的前j个字符所需的最小操作数。
- 创建二维数组
- 初始化边界：
dp[i][0] = i：将word1的前i字符变为空串需删除i次。dp[0][j] = j：将空串变为word2的前j字符需插入j次。
- 状态转移：
- 字符匹配：若
word1[i-1] == word2[j-1]，则dp[i][j] = dp[i-1][j-1]（无需操作）。 - 字符不匹配：取以下三种操作的最小值加 1：
- 删除：
dp[i-1][j] - 插入：
dp[i][j-1] - 替换：
dp[i-1][j-1]
- 删除：
- 字符匹配：若
- 返回结果：
dp[m][n]即为最终编辑距离（m和n为两字符串长度）。
关键洞察
- 最优子结构：
- 当前状态
dp[i][j]仅依赖左方（插入）、上方（删除）、左上方（替换）三个子问题的解。
- 当前状态
- 操作等价性：
- 对
word1的插入操作等价于对word2的删除操作，数学上对称。
- 对
- 空间优化：
- 实际只需维护两行数组（或一行+临时变量），空间可压缩至
O(min(m,n))。
- 实际只需维护两行数组（或一行+临时变量），空间可压缩至
- 实际应用：
- 拼写检查（如 Levenshtein 距离）、DNA 序列比对、自然语言处理中的相似度计算。
复杂度分析
| 类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(m*n) | 需填充 m x n 的 DP 表，每格计算耗时 O(1)。 |
| 空间复杂度 | O(m*n)（基础版） | 完整 DP 表的空间占用。 |
O(min(m,n))（优化版） | 用滚动数组或两行数组优化，仅存储当前行和上一行。 |
代码实现
DP 基础版本
function minDistance(word1, word2) {
const m = word1.length, n = word2.length; const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// 初始化边界条件 for (let i = 0; i <= m; i++) dp[i][0] = i; for (let j = 0; 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] = 1 + Math.min( dp[i - 1][j], // 删除操作 dp[i][j - 1], // 插入操作 dp[i - 1][j - 1] // 替换操作 ); } } }
return dp[m][n];}空间优化，滚动数组
var minDistance = function (word1, word2) { const m = word1.length; const n = word2.length; // 使用一维数组代替二维数组 let dp = new Array(n + 1).fill(0); // 初始化第一行（空字符串到 word2 的前 j 个字符） for (let j = 0; j <= n; j++) { dp[j] = j; } for (let i = 1; i <= m; i++) { // 保存上一行的第一个值（左上角的值） let prev = dp[0]; // 更新当前行的第一个值（第一列） dp[0] = i; for (let j = 1; j <= n; j++) { // 保存当前计算前的 dp[j]（作为下一次的左上角值） let temp = dp[j]; if (word1[i - 1] === word2[j - 1]) { dp[j] = prev; } else { dp[j] = Math.min( dp[j], // 上方（相当于二维数组的 dp[i-1][j]） dp[j - 1], // 左方（相当于二维数组的 dp[i][j-1]） prev // 左上方（相当于二维数组的 dp[i-1][j-1]） ) + 1; } // 更新左上角为当前计算前的值，供下一列使用 prev = temp; } } return dp[n];};