京公网安备11010502063487号给定两个字符串 word1 和 word2，求把 word1 变成 word2 所需的最少操作数，操作只有三种：插入一个字符、删除一个字符、替换一个字符。这是经典的二维动态规划：dp[i][j] 表示 word1 的前 i 个字符变成 word2 的前 j 个字符的最少操作数。如果两个末尾字符相同，不需要操作，等于 dp[i-1][j-1]；否则 1 加上三种操作里最小的：替换（dp[i-1][j-1]）、删除（dp[i-1][j]）、插入（dp[i][j-1]）。本文用真实数据展示"只比较对应位置字符"的直觉写法会错多少，展示不带记忆化的递归调用次数，实测动态规划的耗时，给出五种语言的实现，并把填表做成分步演示。
完整题目见官方页面（链接在文末）。基准解是带记忆化的递归，方向反过来：go(i, j) 表示 word1[i:] 变成 word2[j:] 的最少操作数，从头往后处理，与从前往后填 dp 表的方向不同。一共 14 组用例，覆盖：官方两个示例、两个空串、一个空串、完全相同、完全不同、以及几对经典的例子（kitten → sitting、sunday → saturday）：
输入 ["horse","ros"] 输出 3 输入 ["intention","execution"] 输出 5 输入 ["",""] 输出 0 输入 ["","abc"] 输出 3 输入 ["abc",""] 输出 3 输入 ["a","a"] 输出 0
一个直觉的想法是：把两个字符串对齐，数有多少个位置字符不同，再加上长度差。但插入或删除一个字符之后，后面所有字符的位置都错开了，可能只用一次删除就能让后面全部对齐。下面是这种写法与 solve 的真实结果：
# 「对应位置不同的个数 + 长度差」的写法 'horse' -> 'ros': 该写法 4 solve 3 'intention' -> 'execution': 该写法 5 solve 5 'kitten' -> 'sitting': 该写法 3 solve 3 'abc' -> 'abc': 该写法 0 solve 0 'abcd' -> 'bcd': 该写法 4 solve 1 随机 10000 组：该写法与正确答案不同的有 5028 组（50.3%）
horse → ros 的正确答案是 3，这种写法给出 4；abcd → bcd 只需要删除开头的 a（1 次），而对应位置比较每一位都不同，加上长度差得到 4。随机的 10000 组两个字符串（各长 0 到 9，字母取自 a、b、c）里，这种写法与正确答案不同的有 5028 组，占 50.3%。
最直接的递归是：看两个字符串的末尾，相同就去掉，不同就尝试三种操作，取最小。同一个（word1 的前 i 个，word2 的前 j 个）状态会被重复算很多次。下面是两个长度都为 n、字符完全不同的字符串（这是最坏情形）上真实统计的递归调用次数：
不带记忆化的递归：两个长度都为 n、字符全不同（最坏情形）的字符串 n=4: 结果 4，递归调用 481 次， 0.11 ms；动态规划只有 25 个状态 n=6: 结果 6，递归调用 13483 次， 1.54 ms；动态规划只有 49 个状态 n=8: 结果 8，递归调用 398593 次， 44.42 ms；动态规划只有 81 个状态 n=9: 结果 9，递归调用 2193844 次， 246.48 ms；动态规划只有 100 个状态
n 从 4 增加到 9，递归调用次数从 481 次增加到 2193844 次，耗时从 0.11ms 涨到 246.5ms；而动态规划只有 (n+1)² 个状态（n = 9 时 100 个）。递归调用次数每增加一个 n 大约乘 5（n = 8 到 9 是 5.5 倍），是指数增长。
用两个一维数组滚动：prev 是上一行（word1 的前 i-1 个字符），cur 是当前行。初始时 prev[j] = j（空串变成 word2 前 j 个字符，插入 j 次），每一行开头 cur[0] = i（word1 前 i 个字符变成空串，删除 i 次）。然后对每个 j：末尾字符相同就取 prev[j-1]，否则取 1 + min(prev[j-1]（替换）, prev[j]（删除）, cur[j-1]（插入）)。最后返回 prev[n]。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(word1, word2): m, n = len(word1), len(word2) prev = list(range(n + 1)) # prev[j]：word1 的前 i-1 个字符变成 word2 的前 j 个字符的最少操作数（i=0 时就是插入 j 个字符） for i in range(1, m + 1): cur = [i] + [0] * n # word1 的前 i 个字符变成空串：删除 i 个字符 for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: cur[j] = prev[j - 1] # 末尾字符相同：不需要操作 else: cur[j] = 1 + min(prev[j - 1], # 替换 prev[j], # 删除 word1 的这个字符 cur[j - 1]) # 在 word1 里插入 word2 的这个字符 prev = cur return prev[n]
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["horse","ros"] → 3 ["intention","execution"] → 5 ["",""] → 0 ["","abc"] → 3 ["abc",""] → 3 ["a","a"] → 0
Java · 解法代码class Solution { public int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[] prev = new int[n + 1]; // prev[j]：word1 的前 i-1 个字符变成 word2 的前 j 个字符的最少操作数 for (int j = 0; j <= n; j++) prev[j] = j; // i = 0：插入 j 个字符 for (int i = 1; i <= m; i++) { int[] cur = new int[n + 1]; cur[0] = i; // word1 的前 i 个字符变成空串：删除 i 个字符 for (int j = 1; j <= n; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { cur[j] = prev[j - 1]; // 末尾字符相同：不需要操作 } else { cur[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1])); // 替换、删除、插入 } } prev = cur; } return prev[n]; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["horse","ros"] → 3 ["intention","execution"] → 5 ["",""] → 0 ["","abc"] → 3 ["abc",""] → 3 ["a","a"] → 0
Go · 解法代码func minDistance(word1 string, word2 string) int { m, n := len(word1), len(word2) prev := make([]int, n+1) // prev[j]：word1 的前 i-1 个字符变成 word2 的前 j 个字符的最少操作数 for j := range prev { prev[j] = j // i = 0：插入 j 个字符 } for i := 1; i <= m; i++ { cur := make([]int, n+1) cur[0] = i // word1 的前 i 个字符变成空串：删除 i 个字符 for j := 1; j <= n; j++ { if word1[i-1] == word2[j-1] { cur[j] = prev[j-1] // 末尾字符相同：不需要操作 } else { best := prev[j-1] // 替换 if prev[j] < best { best = prev[j] // 删除 } if cur[j-1] < best { best = cur[j-1] // 插入 } cur[j] = 1 + best } } prev = cur } return prev[n] }
$ go build -o bin . && ./bin < cases.jsonl ["horse","ros"] → 3 ["intention","execution"] → 5 ["",""] → 0 ["","abc"] → 3 ["abc",""] → 3 ["a","a"] → 0
JavaScript · 解法代码function minDistance(word1, word2) { const m = word1.length, n = word2.length; let prev = Array.from({ length: n + 1 }, (_, j) => j); // prev[j]：word1 的前 i-1 个字符变成 word2 的前 j 个字符的最少操作数 for (let i = 1; i <= m; i++) { const cur = new Array(n + 1).fill(0); cur[0] = i; // word1 的前 i 个字符变成空串：删除 i 个字符 for (let j = 1; j <= n; j++) { if (word1[i - 1] === word2[j - 1]) { cur[j] = prev[j - 1]; // 末尾字符相同：不需要操作 } else { cur[j] = 1 + Math.min(prev[j - 1], prev[j], cur[j - 1]); // 替换、删除、插入 } } prev = cur; } return prev[n]; }
$ node run.js < cases.jsonl ["horse","ros"] → 3 ["intention","execution"] → 5 ["",""] → 0 ["","abc"] → 3 ["abc",""] → 3 ["a","a"] → 0
C++ · 解法代码#include <algorithm> #include <string> #include <vector> using namespace std; class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<int> prev(n + 1), cur(n + 1); for (int j = 0; j <= n; j++) prev[j] = j; // i = 0：插入 j 个字符 for (int i = 1; i <= m; i++) { cur[0] = i; // word1 的前 i 个字符变成空串：删除 i 个字符 for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) cur[j] = prev[j - 1]; // 末尾字符相同：不需要操作 else cur[j] = 1 + min({prev[j - 1], prev[j], cur[j - 1]}); // 替换、删除、插入 } swap(prev, cur); } return prev[n]; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["horse","ros"] → 3 ["intention","execution"] → 5 ["",""] → 0 ["","abc"] → 3 ["abc",""] → 3 ["a","a"] → 0
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
两个字符串的长度 n 分别为 50、100、300、1000，字母取自 a、b、c 的规律序列，每个规模取三次中最快的一次。基准是带记忆化的递归（同样是 O(n²) 个状态）：
两个字符串的长度 n | 暴力解 | 本文解法
50 | 0.493 ms | 0.166 ms
100 | 2.169 ms | 0.642 ms
300 | 22.437 ms | 5.899 ms
1000 | （未测，太慢） | 83.560 ms两者都是平方增长：动态规划从 100 到 300（3 倍）耗时增长约 9.2 倍，从 300 到 1000（3.3 倍）增长约 14.2 倍，比理论的 11 倍略高，我没有细究。基准（记忆化递归）在 n = 300 时 22.4ms，动态规划 5.9ms，约 3.8 倍，差距来自递归调用和缓存字典的开销。基准在 n = 1000 时没有再测（递归深度也会很大）。
Python 版本另外和记忆化递归做了随机对拍，两个字符串各长 0 到 9，字母取自 a、b、c：
随机对拍 10000 组（两个各长 0 到 9、字母取自 a、b、c 的随机串），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 horse → ros，答案是 3（horse → rorse（把 h 替换成 r）→ rose（删除一个 r）→ ros（删除 e））。演示里每一步显示一个格子是怎么由左、上、左上三个格子得到的：末尾相同时直接取左上角，不同时取三者最小值再加 1。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。