编辑距离（Edit Distance / Levenshtein Distance）

你用过 git diff 吧？改了几行代码，它就能精准地告诉你"这里删了一行、那里加了一行、还有一行改了几个字"。或者你在搜索引擎里打错了一个字，它依然能猜到你想搜什么，甚至提示你"你是不是想搜 xxx？"。

这些功能的背后，都有一个经典的算法在支撑——编辑距离（Edit Distance），也叫 Levenshtein Distance（莱文斯坦距离）。

为什么需要编辑距离？

假设你在做一个拼写检查器。用户输入了 "helo"，你要在词库里找到最接近的正确单词。怎么定义"最接近"？

最直觉的办法：看把一个字符串变成另一个字符串，最少需要几步操作。每一步操作可以是：

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

"helo" → "hello"    只需插入一个 'l'，距离 = 1
"helo" → "help"     删掉 'o'，插入 'p'，距离 = 2
"helo" → "world"    要改很多，距离 = 5

这个"最少操作步数"就是编辑距离。距离越小，两个字符串越相似。

听起来很简单？但如果你暴力枚举所有可能的操作序列，复杂度是指数级的。这时候，动态规划就派上用场了。

原理拆解

1. 问题定义

给定两个字符串 word1（长度 m）和 word2（长度 n），求将 word1 转换成 word2 所需的最少操作数。允许的操作：插入、删除、替换，每次算 1 步。

2. 状态定义

这是 DP 的灵魂。我们定义：

dp[i][j] = word1 的前 i 个字符 变成 word2 的前 j 个字符 所需的最少操作数

最终答案就是 dp[m][n]。

3. 状态转移方程

考虑 word1[i-1] 和 word2[j-1]（注意是 0-indexed 的第 i 和第 j 个字符）：

情况 A：两个字符相同 → 不需要任何操作，直接继承

dp[i][j] = dp[i-1][j-1]

情况 B：两个字符不同 → 三种操作取最小值

dp[i][j] = 1 + min(
    dp[i-1][j],     // 删除：word1 删掉一个字符，然后看剩下的
    dp[i][j-1],     // 插入：word1 插入一个字符变成 word2 的前 j 个，然后看剩下的
    dp[i-1][j-1]    // 替换：把 word1[i-1] 换成 word2[j-1]
)

用 ASCII 图来理解：

           word2: j-1    j
                    ↓     ↓
word1:  ... a ...  |  ... b ...
        i-1 →      |      ← i
                    |
         (a == b?) ─┤
                    |
         是 → dp[i][j] = dp[i-1][j-1]     // 什么都不用做
         否 → dp[i][j] = 1 + min(          // 三选一
                  dp[i-1][j],              //   删 a
                  dp[i][j-1],              //   插 b
                  dp[i-1][j-1]             //   把 a 换成 b
              )

4. 初始化

边界情况必须想清楚，不然代码准出 bug：

dp[0][0] = 0           // 两个空串，距离为 0
dp[i][0] = i           // word1 前 i 个字符 → 空串，需要删 i 次
dp[0][j] = j           // 空串 → word2 前 j 个字符，需要插 j 次

5. 手动模拟

用 word1 = "horse" 和 word2 = "ros" 来走一遍（LeetCode 72）：

初始化 dp 表格（6行 × 4列）：

        ""    r    o    s
  ""  [  0,   1,   2,   3 ]
  h   [  1,   ?,   ?,   ? ]
  o   [  2,   ?,   ?,   ? ]
  r   [  3,   ?,   ?,   ? ]
  s   [  4,   ?,   ?,   ? ]
  e   [  5,   ?,   ?,   ? ]

逐格填写：

dp[1][1]：'h' vs 'r'，不同 → 1 + min(dp[0][1], dp[1][0], dp[0][0]) = 1 + min(1,1,0) = 1
dp[1][2]：'h' vs 'o'，不同 → 1 + min(dp[0][2], dp[1][1], dp[0][1]) = 1 + min(2,1,1) = 2
dp[1][3]：'h' vs 's'，不同 → 1 + min(dp[0][3], dp[1][2], dp[0][2]) = 1 + min(3,2,2) = 3

dp[2][1]：'o' vs 'r'，不同 → 1 + min(dp[1][1], dp[2][0], dp[1][0]) = 1 + min(1,2,1) = 2
dp[2][2]：'o' vs 'o'，相同！→ dp[1][1] = 1
dp[2][3]：'o' vs 's'，不同 → 1 + min(dp[1][3], dp[2][2], dp[1][2]) = 1 + min(3,1,2) = 2

dp[3][1]：'r' vs 'r'，相同！→ dp[2][0] = 2  ❌ 等等，dp[2][0]=2? 让我重算...
         实际 dp[2][0] = 2（前2个字符→空串要删2次），但 dp[2][1]='o'vs'r'=2
         dp[3][1]：'r'vs'r'，相同 → dp[2][0] = 2

dp[3][2]：'r' vs 'o'，不同 → 1 + min(dp[2][2], dp[3][1], dp[2][1]) = 1 + min(1,2,2) = 2
dp[3][3]：'r' vs 's'，不同 → 1 + min(dp[2][3], dp[3][2], dp[2][2]) = 1 + min(2,2,1) = 2

dp[4][1]：'s' vs 'r'，不同 → 1 + min(dp[3][1], dp[4][0], dp[3][0]) = 1 + min(2,3,3) = 3
dp[4][2]：'s' vs 'o'，不同 → 1 + min(dp[3][2], dp[4][1], dp[3][1]) = 1 + min(2,3,2) = 3
dp[4][3]：'s' vs 's'，相同！→ dp[3][2] = 2

dp[5][1]：'e' vs 'r'，不同 → 1 + min(dp[4][1], dp[5][0], dp[4][0]) = 1 + min(3,4,4) = 4
dp[5][2]：'e' vs 'o'，不同 → 1 + min(dp[4][2], dp[5][1], dp[4][1]) = 1 + min(3,4,3) = 4
dp[5][3]：'e' vs 's'，不同 → 1 + min(dp[4][3], dp[5][2], dp[4][2]) = 1 + min(2,4,3) = 3

最终表格：

        ""    r    o    s
  ""  [  0,   1,   2,   3 ]
  h   [  1,   1,   2,   3 ]
  o   [  2,   2,   1,   2 ]
  r   [  3,   2,   2,   2 ]
  s   [  4,   3,   3,   2 ]
  e   [  5,   4,   4,   3 ]

答案：dp[5][3] = 3

翻译成人话："horse" → "rorse"（替换 h→r）→ "rose"（删除 r）→ "ros"（删除 e），共 3 步。✅

代码实现

TypeScript — 基础二维 DP

function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;

  // dp[i][j] = word1 前 i 个字符 变成 word2 前 j 个字符 的最少操作数
  const dp: number[][] = 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];
}

// 测试
console.log(minDistance("horse", "ros"));       // 3
console.log(minDistance("intention", "execution")); // 5
console.log(minDistance("", "abc"));              // 3
console.log(minDistance("abc", "abc"));           // 0

TypeScript — 空间优化（滚动数组）

上面的二维表用了 O(m×n) 空间。观察状态转移方程，dp[i][j] 只依赖于：

• dp[i-1][j-1]（左上角）
• dp[i-1][j]（正上方）
• dp[i][j-1]（左边）

所以可以用一行数组搞定，空间降到 O(n)：

function minDistanceOptimized(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;

  let prev = new Array(n + 1).fill(0);
  let curr = new Array(n + 1).fill(0);

  // 初始化第一行
  for (let j = 0; j <= n; j++) prev[j] = j;

  for (let i = 1; i <= m; i++) {
    curr[0] = i; // 边界：dp[i][0] = i
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        curr[j] = prev[j - 1];
      } else {
        curr[j] = 1 + Math.min(
          prev[j],       // 删除
          curr[j - 1],   // 插入
          prev[j - 1]    // 替换
        );
      }
    }
    [prev, curr] = [curr, prev]; // 滚动
  }

  return prev[n];
}

如果想进一步压到单数组，需要注意 prev[j-1] 在被覆盖前要先存下来：

function minDistanceSingleArray(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;

  const dp = new Array(n + 1).fill(0);
  for (let j = 0; j <= n; j++) dp[j] = j;

  for (let i = 1; i <= m; i++) {
    let prevDiag = dp[0]; // 保存 dp[i-1][j-1]
    dp[0] = i;
    for (let j = 1; j <= n; j++) {
      const temp = dp[j]; // 先存下来，下一轮会用到
      if (word1[i - 1] === word2[j - 1]) {
        dp[j] = prevDiag;
      } else {
        dp[j] = 1 + Math.min(dp[j], dp[j - 1], prevDiag);
      }
      prevDiag = temp;
    }
  }

  return dp[n];
}

Python 版本

def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    # 二维 DP
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1]   # 替换
                )
    
    return dp[m][n]

# 测试
print(min_distance("horse", "ros"))          # 3
print(min_distance("intention", "execution")) # 5

复杂度分析

版本	时间复杂度	空间复杂度
二维 DP	O(m × n)	O(m × n)
滚动数组	O(m × n)	O(n)
单数组	O(m × n)	O(n)

其中 m 和 n 分别是两个字符串的长度。

💡 面试小贴士：面试时先写二维 DP，确保逻辑正确。如果面试官追问优化，再展示滚动数组。不要一上来就写空间优化版——容易把自己绕晕，面试官也看不懂。

回溯：找出具体操作序列

光知道"最少 3 步"有时候不够，你还想知道具体做了哪些操作。怎么回溯？

从 dp[m][n] 开始，倒着走：

if word1[i-1] == word2[j-1]:
    → 来自 dp[i-1][j-1]，没有操作，斜着走
else:
    → 看 dp[i][j] 是从哪个方向来的：
       来自 dp[i-1][j-1] → 替换
       来自 dp[i-1][j]   → 删除
       来自 dp[i][j-1]   → 插入

function printEditOperations(word1: string, word2: string): string[] {
  const m = word1.length;
  const n = word2.length;
  const dp: number[][] = 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]);
      }
    }
  }

  // 回溯找操作序列
  const ops: string[] = [];
  let i = m, j = n;
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && word1[i - 1] === word2[j - 1]) {
      ops.push(`保留 '${word1[i - 1]}'`);
      i--;
      j--;
    } else if (i > 0 && j > 0 && dp[i][j] === dp[i - 1][j - 1] + 1) {
      ops.push(`替换 '${word1[i - 1]}' → '${word2[j - 1]}'`);
      i--;
      j--;
    } else if (j > 0 && dp[i][j] === dp[i][j - 1] + 1) {
      ops.push(`插入 '${word2[j - 1]}'`);
      j--;
    } else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
      ops.push(`删除 '${word1[i - 1]}'`);
      i--;
    }
  }

  return ops.reverse();
}

// 测试
console.log(printEditOperations("horse", "ros"));
// [
//   "替换 'h' → 'r'",
//   "保留 'o'",
//   "保留 'r'",
//   "删除 's'",
//   "删除 'e'"
// ]

注意：当 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1] 中有多个值相同时，回溯路径不唯一。上面的代码优先走替换，这只是一个合理的 tie-breaking 策略。

变体与进阶

1. 带权重的编辑距离

实际场景中，不同操作的"成本"可能不一样。比如在拼写检查里，键盘上相邻的字母更容易打错（a→s 比 a→z 更常见），替换成本可以设低一些。

// 替换成本不再是固定的 1，而是根据两个字符的距离来算
function substitutionCost(c1: string, c2: string): number {
  const keyboardRow = "qwertyuiopasdfghjklzxcvbnm";
  const idx1 = keyboardRow.indexOf(c1);
  const idx2 = keyboardRow.indexOf(c2);
  const distance = Math.abs(idx1 - idx2);
  return Math.min(distance, 1); // 键盘距离越近，成本越低
}

2. 只允许插入和删除（不许替换）

有些场景下"替换"没有意义（比如 DNA 序列比对，碱基只有 ATCG 四种），可以去掉替换操作：

dp[i][j] = word1[i-1] === word2[j-1]
  ? dp[i-1][j-1]
  : 1 + Math.min(dp[i-1][j], dp[i][j-1]);  // 只有删除和插入

3. Damerau-Levenshtein 距离

在标准编辑距离的基础上，额外允许相邻字符交换（transposition），比如 "ab" → "ba" 算 1 步而不是 2 步（替换 a→b + 替换 b→a）。

这对于拼写检查更友好——人打字经常手快把相邻字母搞反。

实际应用场景

你可能觉得编辑距离只是面试题，但它在工业界到处都是：

1. 拼写纠错

搜索引擎、IDE 的自动补全、手机输入法，都用编辑距离来找"最接近"的候选词。

2. git diff

git diff 的核心算法之一就是编辑距离。它找出两个文件之间的最少增删改操作，然后展示给你看。

3. DNA 序列比对

生物信息学里，DNA 序列（由 A/T/C/G 组成）的相似度比对大量使用编辑距离，用来判断物种之间的亲缘关系。

4. 模糊搜索 / 容错匹配

Elasticsearch 的 fuzzy 查询、PostgreSQL 的 pg_trgm 扩展，底层都用了编辑距离（或其变体）来实现"搜 helo 也能匹配到 hello"。

5. 机器翻译评估

BLEU score 等翻译质量评估指标，与编辑距离的思想一脉相承——衡量生成文本和参考文本之间的"距离"。

相关 LeetCode 题目

题号	题目	难度
72	Edit Distance	Medium
583	Delete Operation for Two Strings	Medium
712	Minimum ASCII Delete Sum for Two Strings	Medium
1143	Longest Common Subsequence	Medium
1035	Uncrossed Lines	Medium

💡 这几道题本质上都是编辑距离的变体或简化版。学会了编辑距离，这些题就是换皮而已。

总结

编辑距离是动态规划中最经典、最实用的算法之一。掌握了它，你不光能解决 LeetCode 上的一串题目，还能理解拼写纠错、git diff、DNA 比对等实际应用背后的原理。

核心记住三点：

1. 状态定义：dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作数
2. 转移方程：字符相同就继承斜对角，不同就三选一取最小（删、插、换）
3. 初始化：dp[i][0] = i，dp[0][j] = j

面试的时候，先画个表格，手动填几个格子，把逻辑理清楚了再写代码。DP 题不怕慢，怕的是没想清楚就动手 😄