示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载导读编辑距离Edit Distance是 LeetCode 上最经典的二维动态规划题目之一本仓库以doocs/leetcode中 0072.Edit Distance 的官方题解为骨架完整讲解问题定义、三种编辑操作、DP 状态设计与转移方程推导并结合仓库内 Python、Java、C、Go、TypeScript、JavaScript 六种语言的参考实现逐行解读。读完本文你将掌握编辑距离问题的完整建模思路、填表手算过程、复杂度分析与多语言编码要点并了解它在拼写纠错、文本 diff 等场景中的延伸应用。题目描述与约束给你两个单词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)约束条件0 word1.length, word2.length 500word1和word2由小写英文字母组成值得注意的是两个单词的长度均可为 0空串因此边界状态必须纳入建模范围长度上限 500 意味着 $O(m \times n)$ 的二维 DP 在时间和空间上都是可接受的。思路演进为什么朴素递归不可行一个直觉做法是递归在word1的每个位置尝试插入、删除或替换三种操作然后递归处理剩余部分取最优结果。这种思路正确但复杂度是指数级的。根本问题在于重叠子问题把word1的前 $i$ 个字符转换成word2的前 $j$ 个字符会被大量不同路径反复求解。当 $m, n \le 500$ 时指数级时间完全无法接受必须寻找多项式级算法。编辑距离问题同时具备两个关键性质最优子结构将前缀 $i$ 变为前缀 $j$ 的最少操作数可以由更短前缀的结果递推得到与如何到达的路径无关重叠子问题不同位置的递推会反复引用同一对前缀的结果。这两点正是动态规划适用性的判据。因此可以按前缀长度递增填表用一张 $(m1) \times (n1)$ 的表保存所有前缀对的答案避免重复计算。动态规划建模状态定义定义 $f[i][j]$ 表示将word1的前 $i$ 个字符转换成word2的前 $j$ 个字符所使用的最少操作数其中 $i \in [1, m], j \in [0, n]$。边界条件空串到任意串只能靠纯插入或纯删除因此有$f[i][0] i$把word1前 $i$ 个字符全部删除$f[0][j] j$向空串中插入word2的前 $j$ 个字符。这两行第一行与第一列是填表的起点对应题目约束中允许空串的情况。状态转移方程考虑 $f[i][j]$分两种情况末尾字符相同若 $word1[i - 1] word2[j - 1]$则最后一个字符无需任何操作只需考虑将word1前 $i - 1$ 个字符转换成word2前 $j - 1$ 个字符即 $$f[i][j] f[i - 1][j - 1]$$末尾字符不同此时三种操作各对应一个相邻状态取三者最小值再加 1本次操作本身删除word1[i - 1]$f[i - 1][j] 1$插入一个与word2[j - 1]相同的字符$f[i][j - 1] 1$将word1[i - 1]替换为word2[j - 1]$f[i - 1][j - 1] 1$即 $$f[i][j] \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) 1$$完整转移方程$$ f[i][j] \begin{cases} i, \textit{if } j 0 \ j, \textit{if } i 0 \ f[i - 1][j - 1], \textit{if } word1[i - 1] word2[j - 1] \ \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) 1, \textit{otherwise} \end{cases} $$最终返回 $f[m][n]$ 即为将整个word1转换成word2的最少操作数。复杂度分析时间复杂度$O(m \times n)$需要填充 $(m1) \times (n1)$ 张表空间复杂度$O(m \times n)$即二维f数组本身。其中 $m$、$n$ 分别为word1与word2的长度。手算推演以 horse → ros 为例用示例 1 完整走一遍填表过程可以直观验证转移方程的正确性。初始化后逐行填写行对应word1前缀列对应word2前缀ros0123h1123o2212r3232s4332e5443关键格点验证f[2][2]ho → ro末尾o o直接继承f[1][1] 1f[3][1]hor → r末尾r r直接继承f[2][0] 2即删除 ho 两个字符f[4][3]hors → ros末尾s s继承f[3][2] 2先把 hor 变成 ro需要 2 步f[5][3]horse → ros末尾e ! s取 $\min(f[4][3], f[5][2], f[4][2]) 1 \min(2, 4, 3) 1 3$。最终结果f[5][3] 3与题目示例完全一致。这张表也印证了 DP 表的内存化效果每个前缀对只计算一次避免了指数量级的重复递归。多语言实现与逐行解读仓库在 solution/0000-0099/0072.Edit Distance 目录下提供了六个独立源码文件Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js与题解文档中 tab 代码块一一对应可直接复制提交。Python3class Solution: def minDistance(self, word1: str, word2: str) - int: m, n len(word1), len(word2) f [[0] * (n 1) for _ in range(m 1)] for j in range(1, n 1): f[0][j] j for i, a in enumerate(word1, 1): f[i][0] i for j, b in enumerate(word2, 1): if a b: f[i][j] f[i - 1][j - 1] else: f[i][j] min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) 1 return f[m][n]实现要点f [[0] * (n 1) for _ in range(m 1)]创建 $(m1) \times (n1)$ 的二维表注意这里必须用列表推导式逐行创建避免[[0] * (n1)] * (m1)造成的行引用共享陷阱先单独初始化第一行f[0][j] j外层enumerate(word1, 1)从 1 开始计数a即word1[i-1]内层同理拿到b每次进入新的一行先写f[i][0] i第一列边界再按列递推末尾字符相等走对角线继承否则取三个相邻状态最小值加 1。Javaclass Solution { public int minDistance(String word1, String word2) { int m word1.length(), n word2.length(); int[][] f new int[m 1][n 1]; for (int j 1; j n; j) { f[0][j] j; } for (int i 1; i m; i) { f[i][0] i; for (int j 1; j n; j) { if (word1.charAt(i - 1) word2.charAt(j - 1)) { f[i][j] f[i - 1][j - 1]; } else { f[i][j] Math.min(f[i - 1][j], Math.min(f[i][j - 1], f[i - 1][j - 1])) 1; } } } return f[m][n]; } }实现要点new int[m 1][n 1]默认全 0因此第一行第一列只需显式写入非 0 的边界值字符比较通过charAt(i - 1)完成Math.min嵌套两次实现三数取最小值。Cclass Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); int f[m 1][n 1]; for (int j 0; j n; j) { f[0][j] j; } for (int i 1; i m; i) { f[i][0] i; for (int j 1; j n; j) { if (word1[i - 1] word2[j - 1]) { f[i][j] f[i - 1][j - 1]; } else { f[i][j] min({f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]}) 1; } } } return f[m][n]; } };实现要点使用栈上变长数组int f[m 1][n 1]第一行从j 0开始初始化三数取最小直接使用 C11 起支持的min({a, b, c})初始化列表重载代码最简洁。Gofunc minDistance(word1 string, word2 string) int { m, n : len(word1), len(word2) f : make([][]int, m1) for i : range f { f[i] make([]int, n1) } for j : 1; j n; j { f[0][j] j } for i : 1; i m; i { f[i][0] i for j : 1; j n; j { if word1[i-1] word2[j-1] { f[i][j] f[i-1][j-1] } else { f[i][j] min(f[i-1][j], min(f[i][j-1], f[i-1][j-1])) 1 } } } return f[m][n] }实现要点Go 没有二维数组字面量初始化需先make外层切片再逐行make内层切片min为 Go 1.21 起内置的内联函数可嵌套使用字符串按下标访问得到的是 byte可直接与另一个 byte 比较。TypeScriptfunction minDistance(word1: string, word2: string): number { const m word1.length; const n word2.length; const f: number[][] Array(m 1) .fill(0) .map(() Array(n 1).fill(0)); for (let j 1; j n; j) { f[0][j] j; } for (let i 1; i m; i) { f[i][0] i; for (let j 1; j n; j) { if (word1[i - 1] word2[j - 1]) { f[i][j] f[i - 1][j - 1]; } else { f[i][j] Math.min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) 1; } } } return f[m][n]; }实现要点通过Array(m 1).fill(0).map(...)生成 $(m1) \times (n1)$ 的二维数组——必须用.map()为每一行创建独立数组否则所有行会共享同一引用Math.min原生支持多参数三数取最小无需嵌套。JavaScript/** * param {string} word1 * param {string} word2 * return {number} */ var minDistance function (word1, word2) { const m word1.length; const n word2.length; const f Array(m 1) .fill(0) .map(() Array(n 1).fill(0)); for (let j 1; j n; j) { f[0][j] j; } for (let i 1; i m; i) { f[i][0] i; for (let j 1; j n; j) { if (word1[i - 1] word2[j - 1]) { f[i][j] f[i - 1][j - 1]; } else { f[i][j] Math.min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) 1; } } } return f[m][n]; };实现要点与 TypeScript 版完全同构去掉了类型标注严格相等比较字符二维数组同样必须逐行.map()创建。若在浏览器或 Node 环境运行直接传入两个字符串调用minDistance(horse, ros)即可得到3。六种实现的共性从源码结构看六份实现Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js遵循完全一致的算法骨架初始化边界行/列 → 双重循环按前缀长度递推 → 末尾字符相等走对角线、不等取三角最小值加 1 → 返回右下角f[m][n]。差异仅体现在语言层面的二维数组创建与min调用方式上体现了同一种 DP 思想在不同语言中的惯用写法。延伸思考还原操作路径与空间优化原文档给出的是求最少操作数的标准二维 DP。基于同一张 DP 表还可以进一步延伸还原具体操作序列从f[m][n]出发反向回溯——若f[i][j] f[i-1][j-1]且字符相等则对角线回退不操作若f[i][j] f[i-1][j-1] 1则回退到左上替换若f[i][j] f[i-1][j] 1则回退到上方删除若f[i][j] f[i][j-1] 1则回退到左方插入。这样即可输出与示例 1、示例 2 中解释部分一致的一步步操作过程。空间优化到 $O(n)$观察转移方程可知f[i][j]只依赖f[i-1][j]上一行同列、f[i][j-1]本行前一列与f[i-1][j-1]上一行前一列三个格点因此只需保留一行数组并缓存左上角旧值即可把空间复杂度从 $O(m \times n)$ 降到 $O(n)$。这也是编辑距离在超长字符串场景如基因序列比对中常用的工程优化。应用场景编辑距离为什么重要编辑距离衡量的是两个字符串之间的相似程度数值越小越相似。它不仅是经典面试题也是真实系统中广泛使用的距离度量拼写纠错搜索引擎与输入法把用户输入与词典中的候选词计算编辑距离距离最小的若干词作为纠错建议文本 diff版本控制系统与文本编辑器计算两版本文本的编辑距离进而展示增删改的行级差异生物信息学DNA / 蛋白质序列比对采用与编辑距离同构的序列比对打分模型允许插入、删除、替换并附不同代价自然语言处理机器翻译评估如 WER、CER 指标、模糊匹配等场景都以编辑距离为基础。在这些场景中动态规划解法或其变体如带权编辑距离、Levenshtein 距离的滚动数组实现都是工程落地的标准手段。总结LeetCode 72「编辑距离」的核心是三步建模状态定义$f[i][j]$ 表示前缀 $i$ 转前缀 $j$ 的最少操作数边界初始化空串侧只含纯插入 / 纯删除$f[i][0] i$、$f[0][j] j$转移方程末尾字符相同继承对角线不同则取删除 / 插入 / 替换三种相邻状态的最小值加 1。掌握这一题后同类的两个序列之间做匹配类 DP 题目如最长公共子序列、正则表达式匹配等都可以套用二维表 分情况转移的框架。仓库题解文档 README.md 及其英文版 README_EN.md 提供了六种语言的完整可提交实现可作为日常复习与对照查阅的权威参考。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐OptiScaler 实战手册3 步替换游戏超采样器免费启用帧生成OptiScaler 实战手册3 步替换游戏超采样器免费启用帧生成 OptiScaler 是开源的超采样替换与帧生成工具以 DLL 注入已支持 DLSS2游戏开发图形学hello-algo 编辑距离问题全解动态规划建模、状态转移方程与空间优化实战hello algo 编辑距离问题全解动态规划建模、状态转移方程与空间优化实战 编辑距离Edit Distance又称 Levenshtein 距离是动文档教程Hello 算法编辑距离问题的动态规划详解与多语言代码实现Hello 算法编辑距离问题的动态规划详解与多语言代码实现 编辑距离Levenshtein 距离是度量两个字符串相似度的经典算法广泛应用于信息检索、拼写文档教程上一篇在 Node.js 中使用 Webpack 打包 uuid完整实战指南下一篇如何快速部署 OpenClaw全平台 3 步上手指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考