编辑距离

更新: 7/4/2026 字数: 0 字 时长: 0 分钟

题目描述

给定两个单词 word1 和 word2，请返回把 word1 转换成 word2 所需的最少操作数。你可以对一个单词进行以下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

例如：word1 = "horse"，word2 = "ros"，最少需要 3 步： horse → rorse（替换 h→r）→ rose（删除 r）→ ros（删除 e）。

这个「最少操作数」也被称为 Levenshtein 距离（莱文斯坦距离），是衡量两个字符串相似度的经典指标。

思路拆解

先想暴力解法

最朴素的想法是递归：定义 solve(i, j) 表示把 word1 的前 i 个字符变成 word2 的前 j 个字符的最小操作数。

• 如果当前两个末尾字符相同（word1[i-1] === word2[j-1]），不用操作，直接看 solve(i-1, j-1)。
• 如果不同，尝试三种操作各走一步，取最小：
  • 替换 → solve(i-1, j-1) + 1
  • 删除 word1 末尾字符 → solve(i-1, j) + 1
  • 在 word1 末尾插入字符 → solve(i, j-1) + 1

点击展开暴力解法（裸递归，指数级）

function minDistanceBrute(word1, word2) {
  const solve = (i, j) => {
    if (i === 0) return j          // word1 空，插 j 次
    if (j === 0) return i          // word2 空，删 i 次
    if (word1[i - 1] === word2[j - 1]) return solve(i - 1, j - 1)
    return 1 + Math.min(
      solve(i - 1, j - 1),         // 替换
      solve(i - 1, j),             // 删除
      solve(i, j - 1)              // 插入
    )
  }
  return solve(word1.length, word2.length)
}

问题在于大量重叠子问题被重复计算，时间复杂度约 ，稍长的字符串就会超时。

推导最优解法：二维 DP

裸递归慢，是因为 solve(i, j) 被反复求解。既然子问题重叠且满足最优子结构，就用一张二维表把每个子问题的答案记下来，这就是动态规划。

定义状态：

边界（base case）：

状态转移：

核心思路

每个格子只依赖三个邻居：左上（替换）、上方（删除）、左方（插入）。字符相同则白拿左上角的值；不同则在三个邻居里挑最小的，再加一次操作。按行从左到右、从上到下填满整张表，右下角就是答案。

三个转移方向的含义，可以对照下图理解——每个格子的值都由它左上、上、左三个方向的邻居决定：

动画演示

下面用样例 word1 = "horse"、word2 = "ros" 完整演示 DP 表的填充过程。每一步会高亮正在计算的格子及其三个来源邻居（黄=左上替换 / 紫=上方删除 / 橙=左方插入），并标出本步选中的最优来源：

动态规划 · 编辑距离演示

样例：word1 = "horse" → word2 = "ros"

当前阶段：准备

	∅	r	o	s
∅
h
o
r
s
e

正在计算左上·替换上方·删除左方·插入本步选中来源

构建 (6) × (4) 的 DP 表。dp[i][j] 表示把 "horse" 的前 i 个字符变成 "ros" 的前 j 个字符所需的最少操作数。

步骤 0 / 17

完整代码

function minDistance(word1, word2) {
  const m = word1.length
  const n = word2.length
  // dp[i][j]：word1 前 i 个字符 → word2 前 j 个字符的最少操作数
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))

  for (let i = 0; i <= m; i++) dp[i][0] = i   // 边界：删 i 次
  for (let j = 0; j <= n; j++) dp[0][j] = 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 - 1],                   // 替换
          dp[i - 1][j],                       // 删除
          dp[i][j - 1]                        // 插入
        )
      }
    }
  }
  return dp[m][n]
}

空间优化

由于 dp[i][j] 只依赖上一行和当前行，可以用滚动数组把空间从 压到 。用一个变量 prev 缓存左上角 dp[i-1][j-1]，就能只保留一行。

复杂度分析

解法	时间复杂度	空间复杂度	说明
裸递归			重叠子问题重复计算，会超时
二维 DP			填满 张表
DP + 滚动数组			只保留一行（或两行）状态

边界与易错点

• 空串边界必须先填：dp[i][0] = i 与 dp[0][j] = j 是递推的基石，漏掉会导致后续全错。
• 索引偏移：dp 表下标从 0 到 m/n，比较字符时用的是 word1[i-1] 与 word2[j-1]（因为第 i 行对应第 i 个字符），差一位是最常见 bug。
• 三个方向别记混：左上=替换、上方=删除（少一个 word1 字符）、左方=插入（多补一个字符），方向搞反答案就错。
• 字符相同不加一：相等时直接继承左上角，切勿再 +1。
• 三个操作代价相等：本题默认插入/删除/替换代价都为 1。若代价不同（带权编辑距离），需把 1 换成对应权重。
• 空串输入：任一单词为空时，答案就是另一个单词的长度，边界逻辑天然覆盖。