72. 编辑距离

题意

给你两个单词 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')

分析

本题我们采用动态规划！

一遇到动态规划的题目，我们往往一开始会找不到方向，想着要不从“起点”一个个换？然

后就会想到利用暴力枚举或者是搜索等方法，但是这类方法的弊端也非常明显——慢！此

类方法解决问题的时间是指数级别的，一旦数据规模变大，所需要的时间我们很可能一下

子就承受不了了。

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

拿例 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]是否一样，如果一样则不需

要再进行任何操作，如果不一样，则需要将其中的一个修改成另外一个。

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

$ f_{[i][j]} = $

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

class Solution {

public int minDistance(String word1, String word2) {

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];

}

}

效率还不错：

1676356531461-74196617-24b4-48b3-a236-fef86741daaf.png

总结

实际上，对于动态规划的题目，往往会把动态转移方程隐藏其中，对题目条件进行抽丝剥

茧，是我们做出这类题目的关键。

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