知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 07 - 编辑距离 ## 题目(LeetCode 72) 给定两个单词,计算将 word1 转换成 word2 所需的最少操作数(插入、删除、替换)。 ``` 输入:word1="horse", word2="ros" 输出:3(horse → rorse → rose → ros) ``` ## 先搞清楚:三种操作是什么 ``` 以 word1="horse" 转换为 word2="ros" 为例: 插入(Insert):在 word1 中插入一个字符 "horse" → "rhorse"(插入 r) 删除(Delete):从 word1 中删除一个字符 "horse" → "orse"(删除 h) 替换(Replace):将 word1 中的一个字符替换为另一个字符 "horse" → "rorse"(h 替换为 r) 目标:用最少的操作次数,把 word1 变成 word2 ``` ## 大白话理解 和 LCS 很像,也是两个字符串逐字符比较。区别是多了"替换"操作。 ``` 比较 word1[i-1] 和 word2[j-1]: 情况 1:字符相同 → 不需要操作,直接看前面的 dp[i][j] = dp[i-1][j-1] 情况 2:字符不同 → 三种操作选最少的 替换:把 word1[i-1] 换成 word2[j-1],然后看 dp[i-1][j-1] 删除:删掉 word1[i-1],然后看 dp[i-1][j] 插入:在 word1[i] 处插入 word2[j-1],然后看 dp[i][j-1] dp[i][j] = min(替换, 删除, 插入) + 1 ``` ### 详解:为什么三种操作对应这三个子问题? 这是整道题最难理解的地方。我们换一个角度来想:**不是"做了什么操作",而是"操作完之后,还剩下什么问题没解决"**。 先建立直觉:dp[i][j] 的含义是"把 word1 的前 i 个字符变成 word2 的前 j 个字符需要几步"。 当 word1[i-1] ≠ word2[j-1] 时,我们必须做一次操作。做完这次操作后,问题变成了哪个子问题?这就是关键。 **关键问题:每种操作之后,word1 的"待处理指针 i"和 word2 的"待处理指针 j"分别怎么变化?** 用具体例子推导,word1="horse",word2="ros",当前看 i=1, j=1,即 word1[0]='h' 和 word2[0]='r',它们不同。 --- **操作一:替换(Replace)** ``` 把 word1[0]='h' 替换成 'r' 操作前:h | o r s e → r | o s ↑ ↑ i=1 j=1 操作后:r 和 r 已经匹配了,这两个字符都"处理完了" 剩下的问题:把 "orse" 变成 "os" ↑ word1 还剩 i-1=0 个字符之后的部分 ↑ word2 还剩 j-1=0 个字符之后的部分 → 剩下的问题 = dp[i-1][j-1] → 总代价 = dp[i-1][j-1] + 1(这一次替换) 记忆方法:替换 = word1 处理了一个,word2 也处理了一个 → i 和 j 都退一格 → dp[i-1][j-1] ``` --- **操作二:删除(Delete)** ``` 把 word1[0]='h' 删掉 操作前:h | o r s e → r | o s ↑ ↑ i=1 j=1 操作后:word1 变成 "orse",word2 还是 "ros"(一个字符都没处理) 剩下的问题:把 "orse" 变成 "ros" ↑ word1 还剩 i-1=0 个字符之后的部分 ↑ word2 还是 j=1 个字符(没动!) → 剩下的问题 = dp[i-1][j] → 总代价 = dp[i-1][j] + 1(这一次删除) 记忆方法:删除 = word1 处理了一个(删掉了),word2 没处理 → 只有 i 退一格,j 不动 → dp[i-1][j] 为什么 word2 没处理? 因为删除操作只是把 word1 的一个字符扔掉了 word2 那边的 'r' 还没有被"匹配"到,还在等着 ``` --- **操作三:插入(Insert)—— 最难理解的一个** ``` 在 word1 当前位置插入 word2[0]='r' 操作前:h | o r s e → r | o s ↑ ↑ i=1 j=1 操作后:word1 变成 "r horse"(在 h 前面插了个 r) 插入的 'r' 和 word2[0]='r' 匹配了! 现在 word2 的第一个字符 'r' 已经被"消耗"了(j 退一格) 但 word1 原来的字符 "horse" 一个都没处理(i 不动) 剩下的问题:把 "horse" 变成 "os" ↑ word1 还是 i=1 个字符(没动!) ↑ word2 还剩 j-1=0 个字符之后的部分 → 剩下的问题 = dp[i][j-1] → 总代价 = dp[i][j-1] + 1(这一次插入) 记忆方法:插入 = word1 没处理(只是加了个新字符),word2 处理了一个 → i 不动,只有 j 退一格 → dp[i][j-1] ``` --- **三种操作的本质对比** ``` 操作 word1 的指针 i word2 的指针 j 对应子问题 ───────────────────────────────────────────────────────── 替换 退一格(-1) 退一格(-1) dp[i-1][j-1] 删除 退一格(-1) 不动(0) dp[i-1][j] 插入 不动(0) 退一格(-1) dp[i][j-1] 为什么最后 +1? 不管哪种操作,都做了「一次操作」,所以操作数 +1 最终公式: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 ↑替换 ↑删除 ↑插入 ``` **用表格位置来记忆(最直观)** ``` dp 表格中,dp[i][j] 的三个邻居: dp[i-1][j-1] dp[i-1][j] dp[i][j-1] dp[i][j] ← 要算这个 左上角 = 替换(两边各退一格) 正上方 = 删除(word1 退一格,word2 不动) 正左方 = 插入(word1 不动,word2 退一格) 取三个邻居的最小值 + 1,就是 dp[i][j] ``` ## 四步法 ``` 第 1 步:dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作数 第 2 步: word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1] word1[i-1] != word2[j-1]:dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 第 3 步: dp[0][j] = j(空串变成长度 j 的串,需要 j 次插入) dp[i][0] = i(长度 i 的串变成空串,需要 i 次删除) 第 4 步:从左到右,从上到下 ``` ## 手动模拟(这是理解的关键) ``` word1 = "horse"(行) word2 = "ros"(列) 初始化: "" r o s "" [ 0 1 2 3 ] ← 空串变成 "r","ro","ros" 需要 1,2,3 次插入 h [ 1 _ _ _ ] o [ 2 _ _ _ ] r [ 3 _ _ _ ] s [ 4 _ _ _ ] e [ 5 _ _ _ ] 逐格填写: dp[1][1]:word1[0]='h', word2[0]='r',不同 替换:dp[0][0]+1 = 0+1 = 1(把 h 换成 r) 删除:dp[0][1]+1 = 1+1 = 2(删掉 h,再把空串变成 "r") 插入:dp[1][0]+1 = 1+1 = 2(把 "h" 变成空串,再插入 r) dp[1][1] = min(1,2,2) = 1 dp[1][2]:word1[0]='h', word2[1]='o',不同 替换:dp[0][1]+1 = 1+1 = 2 删除:dp[0][2]+1 = 2+1 = 3 插入:dp[1][1]+1 = 1+1 = 2 dp[1][2] = 2 dp[1][3]:word1[0]='h', word2[2]='s',不同 替换:dp[0][2]+1 = 2+1 = 3 删除:dp[0][3]+1 = 3+1 = 4 插入:dp[1][2]+1 = 2+1 = 3 dp[1][3] = 3 dp[2][1]:word1[1]='o', word2[0]='r',不同 替换:dp[1][0]+1 = 1+1 = 2 删除:dp[1][1]+1 = 1+1 = 2 插入:dp[2][0]+1 = 2+1 = 3 dp[2][1] = 2 dp[2][2]:word1[1]='o', word2[1]='o',相同! dp[2][2] = dp[1][1] = 1 含义:把 "ho" 变成 "ro" 只需要 1 步(把 h 换成 r) dp[2][3]:word1[1]='o', word2[2]='s',不同 替换:dp[1][2]+1 = 2+1 = 3 删除:dp[1][3]+1 = 3+1 = 4 插入:dp[2][2]+1 = 1+1 = 2 dp[2][3] = 2 dp[3][1]:word1[2]='r', word2[0]='r',相同! dp[3][1] = dp[2][0] = 2 含义:把 "hor" 变成 "r" 需要 2 步(删掉 h 和 o) dp[3][2]:word1[2]='r', word2[1]='o',不同 替换:dp[2][1]+1 = 2+1 = 3 删除:dp[2][2]+1 = 1+1 = 2 插入:dp[3][1]+1 = 2+1 = 3 dp[3][2] = 2 dp[3][3]:word1[2]='r', word2[2]='s',不同 替换:dp[2][2]+1 = 1+1 = 2 删除:dp[2][3]+1 = 2+1 = 3 插入:dp[3][2]+1 = 2+1 = 3 dp[3][3] = 2 dp[4][1]:word1[3]='s', word2[0]='r',不同 替换:dp[3][0]+1 = 3+1 = 4 删除:dp[3][1]+1 = 2+1 = 3 插入:dp[4][0]+1 = 4+1 = 5 dp[4][1] = 3 dp[4][2]:word1[3]='s', word2[1]='o',不同 替换:dp[3][1]+1 = 2+1 = 3 删除:dp[3][2]+1 = 2+1 = 3 插入:dp[4][1]+1 = 3+1 = 4 dp[4][2] = 3 dp[4][3]:word1[3]='s', word2[2]='s',相同! dp[4][3] = dp[3][2] = 2 dp[5][1]:word1[4]='e', word2[0]='r',不同 替换:dp[4][0]+1 = 4+1 = 5 删除:dp[4][1]+1 = 3+1 = 4 插入:dp[5][0]+1 = 5+1 = 6 dp[5][1] = 4 dp[5][2]:word1[4]='e', word2[1]='o',不同 替换:dp[4][1]+1 = 3+1 = 4 删除:dp[4][2]+1 = 3+1 = 4 插入:dp[5][1]+1 = 4+1 = 5 dp[5][2] = 4 dp[5][3]:word1[4]='e', word2[2]='s',不同 替换:dp[4][2]+1 = 3+1 = 4 删除:dp[4][3]+1 = 2+1 = 3 插入:dp[5][2]+1 = 4+1 = 5 dp[5][3] = 3 最终 dp 表格: "" 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 步 ``` ## 代码 ```java public int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[][] dp = new int[m + 1][n + 1]; for (int j = 0; j <= n; j++) dp[0][j] = j; // 空串变成 word2 前 j 个 for (int i = 0; i <= m; i++) dp[i][0] = i; // word1 前 i 个变成空串 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1; } } } return dp[m][n]; } ``` ## 注意:容易困惑的地方 ``` Q:插入和删除是对称的吗? A:是的!对 word1 插入一个字符 = 对 word2 删除一个字符(效果等价) 所以插入和删除的代价相同,都是 1。 Q:dp[i][j] 的含义是"word1 变成 word2"还是"word2 变成 word1"? A:是 word1 前 i 个字符变成 word2 前 j 个字符。 由于插入和删除对称,两个方向的答案相同。 Q:为什么初始化 dp[0][j]=j 而不是 0? A:空串变成长度 j 的串,需要 j 次插入操作,所以是 j。 这是边界条件,不能省略。 ``` ## 一句话总结 字符相同取左上角,不同取三个方向最小值 +1。初始化第一行第一列为 0~n 和 0~m。 --- 上一篇:[06 - 最长公共子序列](./06-lcs.md) | 下一篇:[08 - 最长回文子串](./08-longest-palindrome.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入