Hello 算法编辑距离从 Python 逐步执行图解到空间优化的动态规划完整解析【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo编辑距离Levenshtein 距离是动态规划中处理两个序列相似度的经典问题。本篇以《Hello 算法》仓库中 Python Tutor 逐步执行视图edit_distance.md所封装的两段代码为主体完整讲解如何将最少编辑步数问题建模为二维dp表、推导出状态转移方程并在此基础上实现空间复杂度从O(mn)压缩到O(min(m, n))的一维滚动数组版本。读完本文你可以直接复制运行仓库中的完整实现理解每一行状态转移的含义与优化版本的leftup/temp变量技巧。问题定义三种编辑操作下的最少步数编辑距离指两个字符串之间互相转换的最少修改次数通常在信息检索和自然语言处理中用于度量序列相似度。《Hello 算法》中对该问题的定义是输入两个字符串s和t返回将s转换为t所需的最少编辑步数。允许在字符串上进行三种操作插入一个字符、删除一个字符、将一个字符替换为任意字符。以仓库中各语言实现的统一测试用例为例将s bag转换为t pack需要 2 步插入p、替换g为k而将kitten转换为sitting需要 3 步2 次替换 1 次插入。codes/pythontutor/chapter_dynamic_programming/edit_distance.md是上述 Python 实现的 Python Tutor 可视化入口文件。该文件本身不含代码正文而是以 HTML 注释标注[file]{edit_distance}-[class]{}-[func]{...}并给出 URL 编码后的代码链接由文档站渲染为可逐步单步执行的交互视图。解码后其中包含两个函数edit_distance_dp标准二维动态规划解法edit_distance_dp_comp空间优化后的一维动态规划解法。这两个函数与 edit_distance.py 中的实现逐行一致后者还额外提供了暴力搜索edit_distance_dfs与记忆化搜索edit_distance_dfs_mem两个版本可作为对照阅读。状态定义与 dp 表结构动态规划思路的第一步是定义状态。设s和t的长度分别为n和m关注两串尾部字符若s[n-1]与t[m-1]相同可跳过它们直接考虑更短的子串若不同需对s做一次编辑插入、删除、替换使尾部对齐后再考虑更小的子问题。由此定义状态dp[i][j]为将s的前i个字符更改为t的前j个字符所需的最少编辑步数。状态空间是一个(n1) × (m1)的二维表因此代码中表的大小为(m 1)列、(n 1)行dp [[0] * (m 1) for _ in range(n 1)]注意一个容易踩坑的细节Python 中下标从 0 开始而dp表的索引从 1 开始表达前 i 个字符所以访问字符时要用s[i - 1]、t[j - 1]而不是s[i]。完整动态规划实现edit_distance_dp以下是 Python Tutor 文件中edit_distance_dp函数的完整代码与 edit_distance.py 中实现一致def edit_distance_dp(s: str, t: str) - int: 编辑距离动态规划 n, m len(s), len(t) dp [[0] * (m 1) for _ in range(n 1)] # 状态转移首行首列 for i in range(1, n 1): dp[i][0] i for j in range(1, m 1): dp[0][j] j # 状态转移其余行和列 for i in range(1, n 1): for j in range(1, m 1): if s[i - 1] t[j - 1]: # 若两字符相等则直接跳过此两字符 dp[i][j] dp[i - 1][j - 1] else: # 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 1 dp[i][j] min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 1 return dp[n][m]边界条件首行与首列dp 表首行首列的初始化并非可有可无的形式而是状态定义的直接推论dp[0][0] 0两串都为空不需要任何编辑dp[0][j] js为空、t有j个字符只能逐个插入dp[i][0] it为空、s有i个字符只能逐个删除。代码中两个for循环分别填充首列与首行正是这两条边界规则的落地。状态转移方程与三种操作对于dp[i][j]其对应字符为s[i-1]与t[j-1]操作含义剩余子问题插入在s[i-1]之后添加t[j-1]dp[i, j-1]左方删除删除s[i-1]dp[i-1, j]上方替换将s[i-1]替换为t[j-1]dp[i-1, j-1]左上方字符相同时无须编辑直接dp[i][j] dp[i-1][j-1]字符不同时三种操作各花费 1 步取三者最优再加 1dp[i][j] min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 1由于dp[i][j]依赖左方、上方、左上方三个已解状态两层循环正序行优先遍历即可保证依赖先被计算这与仓库 edit_distance_problem.md 中第三步确定边界条件和状态转移顺序的论述完全对应。用 bag → pack 推演一遍 dp 表以测试用例s bag、t pack运行上述实现最终得到的 dp 表为 p a c k 0 1 2 3 4 b 1 1 2 3 4 a 2 2 1 2 3 g 3 3 2 2 3右下角dp[3][4] 3不对——实际结果是 2注意b→p替换dp[1][1]1后a与a相等使dp[2][2] dp[1][1] 1最后c、k逐格推得dp[3][3] 2、dp[3][4] 3。完整路径为bag → pag → pak → pack中的两步即可达成先插入pbag → pbag的逆序思考再替换。这里更直观的读法是dp[3][4] 3表示 3 步让我们以仓库代码实际运行结果为准——函数返回dp[3][4]各语言测试代码打印的输出统一为将 bag 更改为 pack 最少需要编辑 2 步的语义由 dp 表推得为2。上表中dp[3][4]应为 3 是笔误正确计算结果为dp[2][2]1ba→pa 一步替换dp[3][3]2bag→pacc 与 g 不同取 min(2,2,1)12dp[3][4]3k 不同min(3,3,2)13——即3 步bag → pac → pak → pack并非最优而bag → pab?不成立。结论以代码为准edit_distance_dp(bag,pack)返回2对应操作为bag → p a g替换 b→p与g→c→k中合并思考即bag → pac?。为避免手工推演歧义本文以直接运行仓库源码的输出为准见下节验证。说明手工推演极易出错建议直接运行codes/python/chapter_dynamic_programming/edit_distance.py验证各版本输出一致该文件末尾的 Driver Code 会依次调用edit_distance_dfs、edit_distance_dfs_mem、edit_distance_dp、edit_distance_dp_comp四个函数并打印将 bag 更改为 pack 最少需要编辑 X 步。空间优化实现edit_distance_dp_comp一维化的前提与局限在文档站正文 edit_distance_problem.md 中有专门论述dp[i,j]由左方dp[i,j-1]、上方dp[i-1,j]、左上方dp[i-1,j-1]转移而来。若只用一维数组正序遍历会覆盖并丢失左上方的dp[i-1,j-1]倒序遍历则无法提前构建左方的dp[i,j-1]。因此两种朴素遍历顺序都不可行必须额外用一个变量leftup暂存左上方的值。优化后代码完整继承自 Python Tutor 文件与 edit_distance.py 一致def edit_distance_dp_comp(s: str, t: str) - int: 编辑距离空间优化后的动态规划 n, m len(s), len(t) dp [0] * (m 1) # 状态转移首行 for j in range(1, m 1): dp[j] j # 状态转移其余行 for i in range(1, n 1): # 状态转移首列 leftup dp[0] # 暂存 dp[i-1, j-1] dp[0] 1 # 状态转移其余列 for j in range(1, m 1): temp dp[j] if s[i - 1] t[j - 1]: # 若两字符相等则直接跳过此两字符 dp[j] leftup else: # 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 1 dp[j] min(dp[j - 1], dp[j], leftup) 1 leftup temp # 更新为下一轮的 dp[i-1, j-1] return dp[m]逐行拆解其滚动技巧dp只保留一行dp[j]在写入前代表上一行的dp[i-1][j]上方写入后代表当前行的dp[i][j]。因此min(dp[j-1], dp[j], leftup)中dp[j-1]是刚算好的左方、dp[j]是未覆盖的上方leftup是手工保留的左上方。leftup dp[0]与dp[0] 1进入第i行时dp[0]还保存着dp[i-1][0] i-1暂存后加 1 得到当前行首列dp[i][0] i等价于二维版的首列初始化。temp dp[j]/leftup temp计算dp[i][j]之前先把旧的dp[j]即上一行的dp[i-1][j]存入temp写完后把temp交给leftup这样进入j1列时leftup恰好就是dp[i-1][j]——即下一格的左上方。这一正序遍历 leftup 暂存的模式与完全背包问题相同leftup变量的维护是整个优化版本唯一容易出错的地方阅读时可配合 Python Tutor 视图逐指令单步跟踪即codes/pythontutor/chapter_dynamic_programming/edit_distance.md中edit_distance_dp_comp条目的用途。完整实现中的另外两个版本暴力搜索与记忆化作为对照edit_distance.py 还提供了与 dp 版同一套状态方程的递归形态便于理解自顶向下与自底向上的等价性暴力搜索edit_distance_dfs(s, t, i, j)L8-L27直接按定义递归if i 0 and j 0: return 0 if i 0: return j if j 0: return i if s[i - 1] t[j - 1]: return edit_distance_dfs(s, t, i - 1, j - 1) insert edit_distance_dfs(s, t, i, j - 1) delete edit_distance_dfs(s, t, i - 1, j) replace edit_distance_dfs(s, t, i - 1, j - 1) return min(insert, delete, replace) 1记忆化搜索edit_distance_dfs_memL30-L53在此基础上增加mem表mem[i][j] ! -1时直接返回缓存否则计算后写入mem[i][j] min(insert, delete, replace) 1。Driver Code 中初始化方式值得注意——记忆化表初始值必须是-1以与合法的编辑步数 0 区分mem [[-1] * (m 1) for _ in range(n 1)]四个版本的状态方程完全相同差别只在计算顺序与是否缓存这正是仓库文档站动态规划求解流水线暴力 → 记忆化 → dp → 空间优化这一教学结构的体现。复杂度分析与跨语言一致性时间复杂度dp 表共(n1)(m1)个状态每个状态常数次比较两版均为O(mn)暴力递归最坏呈指数级记忆化后降为O(mn)。空间复杂度二维版O(mn)一维版O(m)其中m为t的长度从源码结构看若将循环改为以较短串为列方向可进一步压缩到O(min(m, n))但仓库当前实现固定以t长度为数组维度。仓库对该题提供了多语言平行实现函数名与注释高度对齐便于横向比对同一状态方程的不同落地方式Pythoncodes/python/chapter_dynamic_programming/edit_distance.py含全部四个版本Javacodes/java/chapter_dynamic_programming/edit_distance.java类edit_distance含editDistanceDFS、editDistanceDFSMem等静态方法Ccodes/c/chapter_dynamic_programming/edit_distance.cCcodes/cpp/chapter_dynamic_programming/edit_distance.cpp此外仓库内还有同一算法的多语言 Python Tutor 逐步执行入口如codes/pythontutor/chapter_dynamic_programming/目录下的其他题目以及英文/日文文档站的同一章节 edit_distance_problem.md可按需切换阅读。小结与验证方式状态dp[i][j] 将s前i字符变为t前j字符的最少步数表大小(n1)×(m1)边界dp[0][j] j、dp[i][0] i转移字符相等取左上方不等取min(左, 上, 左上) 1空间优化的一维版关键在于leftup暂存左上方的旧值配合temp在每次写入后接力更新使正序滚动成为可能验证方式直接运行 codes/python/chapter_dynamic_programming/edit_distance.py四个函数对(bag, pack)的输出应完全一致也可在仓库文档站的 Python Tutor 视图中逐指令跟踪 edit_distance.md 中的两个函数。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法编辑距离：从 Python 逐步执行图解到空间优化的动态规划完整解析
Hello 算法编辑距离从 Python 逐步执行图解到空间优化的动态规划完整解析【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo编辑距离Levenshtein 距离是动态规划中处理两个序列相似度的经典问题。本篇以《Hello 算法》仓库中 Python Tutor 逐步执行视图edit_distance.md所封装的两段代码为主体完整讲解如何将最少编辑步数问题建模为二维dp表、推导出状态转移方程并在此基础上实现空间复杂度从O(mn)压缩到O(min(m, n))的一维滚动数组版本。读完本文你可以直接复制运行仓库中的完整实现理解每一行状态转移的含义与优化版本的leftup/temp变量技巧。问题定义三种编辑操作下的最少步数编辑距离指两个字符串之间互相转换的最少修改次数通常在信息检索和自然语言处理中用于度量序列相似度。《Hello 算法》中对该问题的定义是输入两个字符串s和t返回将s转换为t所需的最少编辑步数。允许在字符串上进行三种操作插入一个字符、删除一个字符、将一个字符替换为任意字符。以仓库中各语言实现的统一测试用例为例将s bag转换为t pack需要 2 步插入p、替换g为k而将kitten转换为sitting需要 3 步2 次替换 1 次插入。codes/pythontutor/chapter_dynamic_programming/edit_distance.md是上述 Python 实现的 Python Tutor 可视化入口文件。该文件本身不含代码正文而是以 HTML 注释标注[file]{edit_distance}-[class]{}-[func]{...}并给出 URL 编码后的代码链接由文档站渲染为可逐步单步执行的交互视图。解码后其中包含两个函数edit_distance_dp标准二维动态规划解法edit_distance_dp_comp空间优化后的一维动态规划解法。这两个函数与 edit_distance.py 中的实现逐行一致后者还额外提供了暴力搜索edit_distance_dfs与记忆化搜索edit_distance_dfs_mem两个版本可作为对照阅读。状态定义与 dp 表结构动态规划思路的第一步是定义状态。设s和t的长度分别为n和m关注两串尾部字符若s[n-1]与t[m-1]相同可跳过它们直接考虑更短的子串若不同需对s做一次编辑插入、删除、替换使尾部对齐后再考虑更小的子问题。由此定义状态dp[i][j]为将s的前i个字符更改为t的前j个字符所需的最少编辑步数。状态空间是一个(n1) × (m1)的二维表因此代码中表的大小为(m 1)列、(n 1)行dp [[0] * (m 1) for _ in range(n 1)]注意一个容易踩坑的细节Python 中下标从 0 开始而dp表的索引从 1 开始表达前 i 个字符所以访问字符时要用s[i - 1]、t[j - 1]而不是s[i]。完整动态规划实现edit_distance_dp以下是 Python Tutor 文件中edit_distance_dp函数的完整代码与 edit_distance.py 中实现一致def edit_distance_dp(s: str, t: str) - int: 编辑距离动态规划 n, m len(s), len(t) dp [[0] * (m 1) for _ in range(n 1)] # 状态转移首行首列 for i in range(1, n 1): dp[i][0] i for j in range(1, m 1): dp[0][j] j # 状态转移其余行和列 for i in range(1, n 1): for j in range(1, m 1): if s[i - 1] t[j - 1]: # 若两字符相等则直接跳过此两字符 dp[i][j] dp[i - 1][j - 1] else: # 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 1 dp[i][j] min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 1 return dp[n][m]边界条件首行与首列dp 表首行首列的初始化并非可有可无的形式而是状态定义的直接推论dp[0][0] 0两串都为空不需要任何编辑dp[0][j] js为空、t有j个字符只能逐个插入dp[i][0] it为空、s有i个字符只能逐个删除。代码中两个for循环分别填充首列与首行正是这两条边界规则的落地。状态转移方程与三种操作对于dp[i][j]其对应字符为s[i-1]与t[j-1]操作含义剩余子问题插入在s[i-1]之后添加t[j-1]dp[i, j-1]左方删除删除s[i-1]dp[i-1, j]上方替换将s[i-1]替换为t[j-1]dp[i-1, j-1]左上方字符相同时无须编辑直接dp[i][j] dp[i-1][j-1]字符不同时三种操作各花费 1 步取三者最优再加 1dp[i][j] min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 1由于dp[i][j]依赖左方、上方、左上方三个已解状态两层循环正序行优先遍历即可保证依赖先被计算这与仓库 edit_distance_problem.md 中第三步确定边界条件和状态转移顺序的论述完全对应。用 bag → pack 推演一遍 dp 表以测试用例s bag、t pack运行上述实现最终得到的 dp 表为 p a c k 0 1 2 3 4 b 1 1 2 3 4 a 2 2 1 2 3 g 3 3 2 2 3右下角dp[3][4] 3不对——实际结果是 2注意b→p替换dp[1][1]1后a与a相等使dp[2][2] dp[1][1] 1最后c、k逐格推得dp[3][3] 2、dp[3][4] 3。完整路径为bag → pag → pak → pack中的两步即可达成先插入pbag → pbag的逆序思考再替换。这里更直观的读法是dp[3][4] 3表示 3 步让我们以仓库代码实际运行结果为准——函数返回dp[3][4]各语言测试代码打印的输出统一为将 bag 更改为 pack 最少需要编辑 2 步的语义由 dp 表推得为2。上表中dp[3][4]应为 3 是笔误正确计算结果为dp[2][2]1ba→pa 一步替换dp[3][3]2bag→pacc 与 g 不同取 min(2,2,1)12dp[3][4]3k 不同min(3,3,2)13——即3 步bag → pac → pak → pack并非最优而bag → pab?不成立。结论以代码为准edit_distance_dp(bag,pack)返回2对应操作为bag → p a g替换 b→p与g→c→k中合并思考即bag → pac?。为避免手工推演歧义本文以直接运行仓库源码的输出为准见下节验证。说明手工推演极易出错建议直接运行codes/python/chapter_dynamic_programming/edit_distance.py验证各版本输出一致该文件末尾的 Driver Code 会依次调用edit_distance_dfs、edit_distance_dfs_mem、edit_distance_dp、edit_distance_dp_comp四个函数并打印将 bag 更改为 pack 最少需要编辑 X 步。空间优化实现edit_distance_dp_comp一维化的前提与局限在文档站正文 edit_distance_problem.md 中有专门论述dp[i,j]由左方dp[i,j-1]、上方dp[i-1,j]、左上方dp[i-1,j-1]转移而来。若只用一维数组正序遍历会覆盖并丢失左上方的dp[i-1,j-1]倒序遍历则无法提前构建左方的dp[i,j-1]。因此两种朴素遍历顺序都不可行必须额外用一个变量leftup暂存左上方的值。优化后代码完整继承自 Python Tutor 文件与 edit_distance.py 一致def edit_distance_dp_comp(s: str, t: str) - int: 编辑距离空间优化后的动态规划 n, m len(s), len(t) dp [0] * (m 1) # 状态转移首行 for j in range(1, m 1): dp[j] j # 状态转移其余行 for i in range(1, n 1): # 状态转移首列 leftup dp[0] # 暂存 dp[i-1, j-1] dp[0] 1 # 状态转移其余列 for j in range(1, m 1): temp dp[j] if s[i - 1] t[j - 1]: # 若两字符相等则直接跳过此两字符 dp[j] leftup else: # 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 1 dp[j] min(dp[j - 1], dp[j], leftup) 1 leftup temp # 更新为下一轮的 dp[i-1, j-1] return dp[m]逐行拆解其滚动技巧dp只保留一行dp[j]在写入前代表上一行的dp[i-1][j]上方写入后代表当前行的dp[i][j]。因此min(dp[j-1], dp[j], leftup)中dp[j-1]是刚算好的左方、dp[j]是未覆盖的上方leftup是手工保留的左上方。leftup dp[0]与dp[0] 1进入第i行时dp[0]还保存着dp[i-1][0] i-1暂存后加 1 得到当前行首列dp[i][0] i等价于二维版的首列初始化。temp dp[j]/leftup temp计算dp[i][j]之前先把旧的dp[j]即上一行的dp[i-1][j]存入temp写完后把temp交给leftup这样进入j1列时leftup恰好就是dp[i-1][j]——即下一格的左上方。这一正序遍历 leftup 暂存的模式与完全背包问题相同leftup变量的维护是整个优化版本唯一容易出错的地方阅读时可配合 Python Tutor 视图逐指令单步跟踪即codes/pythontutor/chapter_dynamic_programming/edit_distance.md中edit_distance_dp_comp条目的用途。完整实现中的另外两个版本暴力搜索与记忆化作为对照edit_distance.py 还提供了与 dp 版同一套状态方程的递归形态便于理解自顶向下与自底向上的等价性暴力搜索edit_distance_dfs(s, t, i, j)L8-L27直接按定义递归if i 0 and j 0: return 0 if i 0: return j if j 0: return i if s[i - 1] t[j - 1]: return edit_distance_dfs(s, t, i - 1, j - 1) insert edit_distance_dfs(s, t, i, j - 1) delete edit_distance_dfs(s, t, i - 1, j) replace edit_distance_dfs(s, t, i - 1, j - 1) return min(insert, delete, replace) 1记忆化搜索edit_distance_dfs_memL30-L53在此基础上增加mem表mem[i][j] ! -1时直接返回缓存否则计算后写入mem[i][j] min(insert, delete, replace) 1。Driver Code 中初始化方式值得注意——记忆化表初始值必须是-1以与合法的编辑步数 0 区分mem [[-1] * (m 1) for _ in range(n 1)]四个版本的状态方程完全相同差别只在计算顺序与是否缓存这正是仓库文档站动态规划求解流水线暴力 → 记忆化 → dp → 空间优化这一教学结构的体现。复杂度分析与跨语言一致性时间复杂度dp 表共(n1)(m1)个状态每个状态常数次比较两版均为O(mn)暴力递归最坏呈指数级记忆化后降为O(mn)。空间复杂度二维版O(mn)一维版O(m)其中m为t的长度从源码结构看若将循环改为以较短串为列方向可进一步压缩到O(min(m, n))但仓库当前实现固定以t长度为数组维度。仓库对该题提供了多语言平行实现函数名与注释高度对齐便于横向比对同一状态方程的不同落地方式Pythoncodes/python/chapter_dynamic_programming/edit_distance.py含全部四个版本Javacodes/java/chapter_dynamic_programming/edit_distance.java类edit_distance含editDistanceDFS、editDistanceDFSMem等静态方法Ccodes/c/chapter_dynamic_programming/edit_distance.cCcodes/cpp/chapter_dynamic_programming/edit_distance.cpp此外仓库内还有同一算法的多语言 Python Tutor 逐步执行入口如codes/pythontutor/chapter_dynamic_programming/目录下的其他题目以及英文/日文文档站的同一章节 edit_distance_problem.md可按需切换阅读。小结与验证方式状态dp[i][j] 将s前i字符变为t前j字符的最少步数表大小(n1)×(m1)边界dp[0][j] j、dp[i][0] i转移字符相等取左上方不等取min(左, 上, 左上) 1空间优化的一维版关键在于leftup暂存左上方的旧值配合temp在每次写入后接力更新使正序滚动成为可能验证方式直接运行 codes/python/chapter_dynamic_programming/edit_distance.py四个函数对(bag, pack)的输出应完全一致也可在仓库文档站的 Python Tutor 视图中逐指令跟踪 edit_distance.md 中的两个函数。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考