072.编辑距离

作者：沉默王二
发布时间：2023-02-14T14:36:39.770+0800

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

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

难度

困难

示例

示例 1：

输入：word1 = "horse", word2 = "ros"

解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"

解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')

分析

本题我们采用动态规划！

一遇到动态规划的题目，我们往往一开始会找不到方向，想着要不从“起点”一个个换？然后就会想到利用暴力枚举或者是搜索等方法，但是这类方法的弊端也非常明显——慢！此类方法解决问题的时间是指数级别的，一旦数据规模变大，所需要的时间我们很可能一下子就承受不了了。

既然如此，我们不妨换个思路，从 “终点” 往前看。

拿例1来稍作说明：

rose 要转变为 ros，只需要 1 步；我们假设 horse 转换到 rose 至少需要 d 次操作，那么horse 到 ros 的操作次数就是 d + 1。

这样反过来看，看最终状态的前一个状态最少需要多少步骤，那么最终状态的答案就能由最终状态的前一个状态转化而来，以此类推，我们只需要这样子依次去求每个状态的前一个状态就可以知道它本身了，这，就是递推。

不断拆分子问题的过程，就能逐渐接近正确答案。

来考虑动态规划：

首先假设 f[i][j] 为将 word1 的前 i 位与 word2 的前 j 位变得一样的最少操作数。

那么显而易见，f[0][0]为0，因为空串和空串是一样的，接着如果是f[0][j]和f[i][0]也必然为j和i，因为空字符串变成任意一个字符串最少的操作次数的方案必然是空串一个个添加成该字符串，或者是该字符串一个个减少成空串。

初始条件解决了，接下来就要考虑每个状态之间怎么转移。

现在考虑f[i][j]的值，并且f[i - 1][j]、f[i - 1][j - 1] 和 f[i][j - 1]均在之前以及求出来了。

那么f[i][j]的取值则有三种可能：

f[i - 1][j] + 1 : 我们知道f[i - 1][j]代表的是word1[0~(i-1)]和word2[0~j]变成一样的最少操作次数，那么这时候我们只需要在word1后面添加一个，或者是word2删除一个即可使两个一样。
f[i][j - 1] + 1 : 我们知道f[i][j - 1]代表的是word1[0~i]和word2[0~(j-1)]变成一样的最少操作次数，那么这时候我们只需要在word1删除一个，或者是word2后面添加一个即可使两个一样。
f[i - 1][j - 1] + 1 或 f[i - 1][j - 1] : 如果word1[0~(i-1)]和word2[0~(j-1)]已经修改成一样了，那么就只需要考虑word1[i]和word2[j]是否一样，如果一样则不需要再进行任何操作，如果不一样，则需要将其中的一个修改成另外一个。

这样子，我们就完成了所有状态转移的讨论，我们的状态转移方程也浮现出来了

这时候我们就能写出如下的代码了

class Solution {

int n = word1.length(),m = word2.length(); int[][] f = new int[n + 1][m + 1]; for(int i = 0;i <= n;i++){ for(int j = 0;j <= m;j++){ if(i == 0){ f[i][j] = j; continue; } if(j == 0){ f[i][j] = i; continue; } f[i][j] = Math.min(f[i][j - 1] + 1,Math.min(f[i - 1][j] + 1,f[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1))); } } return f[n][m]; }}

效率还不错：

总结

实际上，对于动态规划的题目，往往会把动态转移方程隐藏其中，对题目条件进行抽丝剥茧，是我们做出这类题目的关键。

力扣链接：( https://leetcode.cn/problems/edit-distance/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

题意

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

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

难度

困难

示例

示例 1：

输入：word1 = "horse", word2 = "ros"

解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"

分析

本题我们采用动态规划！

既然如此，我们不妨换个思路，从 “终点” 往前看。

拿例1来稍作说明：

rose 要转变为 ros，只需要 1 步；我们假设 horse 转换到 rose 至少需要 d 次操作，那么horse 到 ros 的操作次数就是 d + 1。

不断拆分子问题的过程，就能逐渐接近正确答案。

来考虑动态规划：

首先假设 f[i][j] 为将 word1 的前 i 位与 word2 的前 j 位变得一样的最少操作数。

初始条件解决了，接下来就要考虑每个状态之间怎么转移。

现在考虑f[i][j]的值，并且f[i - 1][j]、f[i - 1][j - 1] 和 f[i][j - 1]均在之前以及求出来了。

那么f[i][j]的取值则有三种可能：

f[i - 1][j] + 1 : 我们知道f[i - 1][j]代表的是word1[0~(i-1)]和word2[0~j]变成一样的最少操作次数，那么这时候我们只需要在word1后面添加一个，或者是word2删除一个即可使两个一样。
f[i][j - 1] + 1 : 我们知道f[i][j - 1]代表的是word1[0~i]和word2[0~(j-1)]变成一样的最少操作次数，那么这时候我们只需要在word1删除一个，或者是word2后面添加一个即可使两个一样。
f[i - 1][j - 1] + 1 或 f[i - 1][j - 1] : 如果word1[0~(i-1)]和word2[0~(j-1)]已经修改成一样了，那么就只需要考虑word1[i]和word2[j]是否一样，如果一样则不需要再进行任何操作，如果不一样，则需要将其中的一个修改成另外一个。

这样子，我们就完成了所有状态转移的讨论，我们的状态转移方程也浮现出来了

这时候我们就能写出如下的代码了

class Solution {

效率还不错：

总结

实际上，对于动态规划的题目，往往会把动态转移方程隐藏其中，对题目条件进行抽丝剥茧，是我们做出这类题目的关键。

力扣链接：( https://leetcode.cn/problems/edit-distance/

一步一个脚印

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

题意

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

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

难度

困难

示例

示例 1：

输入：word1 = "horse", word2 = "ros"

解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"

分析

本题我们采用动态规划！

既然如此，我们不妨换个思路，从 “终点” 往前看。

拿例1来稍作说明：

rose 要转变为 ros，只需要 1 步；我们假设 horse 转换到 rose 至少需要 d 次操作，那么horse 到 ros 的操作次数就是 d + 1。

不断拆分子问题的过程，就能逐渐接近正确答案。

来考虑动态规划：

首先假设 f[i][j] 为将 word1 的前 i 位与 word2 的前 j 位变得一样的最少操作数。

初始条件解决了，接下来就要考虑每个状态之间怎么转移。

现在考虑f[i][j]的值，并且f[i - 1][j]、f[i - 1][j - 1] 和 f[i][j - 1]均在之前以及求出来了。

那么f[i][j]的取值则有三种可能：

f[i - 1][j] + 1 : 我们知道f[i - 1][j]代表的是word1[0~(i-1)]和word2[0~j]变成一样的最少操作次数，那么这时候我们只需要在word1后面添加一个，或者是word2删除一个即可使两个一样。
f[i][j - 1] + 1 : 我们知道f[i][j - 1]代表的是word1[0~i]和word2[0~(j-1)]变成一样的最少操作次数，那么这时候我们只需要在word1删除一个，或者是word2后面添加一个即可使两个一样。
f[i - 1][j - 1] + 1 或 f[i - 1][j - 1] : 如果word1[0~(i-1)]和word2[0~(j-1)]已经修改成一样了，那么就只需要考虑word1[i]和word2[j]是否一样，如果一样则不需要再进行任何操作，如果不一样，则需要将其中的一个修改成另外一个。

这样子，我们就完成了所有状态转移的讨论，我们的状态转移方程也浮现出来了

这时候我们就能写出如下的代码了

class Solution {

效率还不错：

总结

实际上，对于动态规划的题目，往往会把动态转移方程隐藏其中，对题目条件进行抽丝剥茧，是我们做出这类题目的关键。

力扣链接：( https://leetcode.cn/problems/edit-distance/

一步一个脚印

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412