微软又考了这道题
大家好，我是吴师兄。
今天分享的题目是 LeetCode 72. 编辑距离。
我发现这道题目外企非常喜欢考，亚马逊和微软考察的频率非常高。
来看这道题目的描述：
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 1、插入一个字符
- 2、删除一个字符
- 3、替换一个字符
比如 word1 单词是 horse，而 word2 单词是 ros。
那么 word1 可以通过如下的转换变为 word2 ：
先把 horse 开头的 h 替换为 r ，成为一个新的单词 rorse，接着把第二个 r 删除，变成了 rose，最后再删除 e 就转换为目标单词 ros。
解题思路就是利用动态规划，找出状态转移方程。
图片来源于算法训练营课件
具体可以这样分析。
我们想知道从 word1[0..i] 到 word2[0..j] 的变换需要几步，而从 word1[0..i] 到 word2[0..j]可以通过以下三种情况变化而来。
1、先从 word1[0..i-1] 转换为 word2[0..j-1] ，假设这个过程需要 k 步，转换完毕之后，再执行替换操作，将 word1[i] 改成 word2[j]，如果出现特殊情况 word1[i] 恰巧等于 word2[j]，那么执行 k 步后就成功了，否则还需要再执行一下替换操作，总共需要 k + 1 步。
2、先从 word1[0..i-1] 转换为 word2[0..j] ，假设这个过程需要 k 步，转换完毕之后，再执行删除操作，把原先在 word1 中最后的那个字符 word1[i] 删除掉，总共需要 k + 1 步。
3、先从 word1[0..i] 转换为 word2[0..j-1] ，假设这个过程需要 k 步，转换完毕之后，再执行插入操作，把原先在 word2 中最后的那个字符 word2[j] 插入到 word1 中，总共需要 k + 1 步。
基于这三种情况，哪种方案少就选哪种就行。
看看代码吧，注释比较多，代码可以左右滑动查看。
class Solution {
public int minDistance(String word1, String word2) {
// 获取字符串 word1 的长度
int L1 = word1.length();
// 获取字符串 word2 的长度
int L2 = word2.length();
// 设置二维数组 dp 用来储存 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
// dp[0][0] 表示 word1 的前 0 个字符转换为 word2 的前 0 个字符最少操作数
// dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
// dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
// dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
// dp[L1][L2] 表示 word1 的前 L1 个字符转换为 word2 的前 L2 个字符最少操作数
int[][] dp = new int[L1+1][L2+1];
// dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
// dp[i][0] 相当于给二维数组 dp 的第一列进行赋值操作
// 只需要每次执行删除操作，就可以把 word1 的字符删除到 0 个字符
for(int i = 0 ; i <= L1 ; i++){
// dp[1][0] 表示需要删除 1 次才能删除到 0 个字符
// dp[2][0] 表示需要删除 2 次才能删除到 2 个字符
// dp[i][0] 表示需要删除 i 次才能删除到 i 个字符
dp[i][0] = i;
}
// dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
// dp[0][j] 相当于给二维数组 dp 的第一行进行赋值操作
// 只需要每次执行插入操作，就可以把 word1 的字符转行为 j 个字符
for(int j = 0 ; j <= L2 ;j++){
// dp[0][1] 表示需要插入 1 次才能得到 1 个字符
// dp[0][2] 表示需要插入 2 次才能得到 2 个字符
// dp[0][j] 表示需要插入 j 次才能得到 j 个字符
dp[0][j] = j;
}
// 通过两个 for 循环，设置二维数组 dp 中的所有元素的值
// i 从 word1 的第 1 个字符一直到 L1 个字符
for(int i = 1 ; i <= L1 ;i++){
// j 从 word2 的第 1 个字符一直到 L2 个字符
for(int j = 1 ; j <= L2;j++){
// 二维数组 dp 的下标是从 (0,0) 开始的
// 所以 dp[i][j] 表示的是 word1 中前 i 个字符即位置为 i - 1 的字符
// 转换为 word2 中前 j 个字符即位置为 j - 1 的字符所需要的最少操作数
// 如果此时 word1 中第 i - 1 个位置的字符（即当前遍历 i 时的字符）
// 与 word2 中第 j - 1 个位置的字符【相等】（即当前遍历 j 时的字符）
// 说明 word1 的前 i - 1 个字符转换为 word2 中前 j - 1 个字符成功后，
// word1 的前 i 个字符也就成功转换为 word2 的前 j 个字符了
if(word1.charAt(i-1) == word2.charAt(j-1)){
// dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
// dp[i - 1][j - 1] 表示 word1 的前 i - 1 个字符转换为 word2 的前 j -1 个字符最少操作数
// 比如 word1 为 abcd，word2 为 efgd
// 此时 i = 4，j = 4
// 由于 word1.charAt(4 - 1) = d
// word2.charAt(4 - 1) = d
// 所以如果知道了 abc 转换为 efg 的最少操作数，那么结果也就出来了
// d --> d 不需要执行任何操作
// dp[i][j] = dp[i-1][j-1];
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j] + 1,dp[i][j-1] + 1)) ;
// 否则，说明 word1 中第 i - 1 个位置的字符（即当前遍历 i 时的字符）
// 与 word2 中第 j - 1 个位置的字符【不相等】（即当前遍历 j 时的字符）
}else{
// 那么 dp[i][j] 可以从以下三种状态转换过来
// 1、word1(L1-1) ——> word2(L2-1)
// 2、word1(L1-1) ——> word2(L2)
// 3、word1(L1) ——> word2(L2-1)
// word1(L1-1) ——> word2(L2-1) 的最少操作数是 dp[i - 1][j - 1]
// word1(L1-1) ——> word2(L2) 的最少操作数是 dp[i - 1][j]
// word1(L1) ——> word2(L2-1) 的最少操作数是 dp[i][j - 1])
// 选这三种状态的较小值后，
// 1、如果是 word1(L1-1) ——> word2(L2-1) 过来的，再执行 1 次替换操作
// 2、如果是 word1(L1-1) ——> word2(L2) 过来的，再执行 1 次删除操作
// 3、如果是 word1(L1) ——> word2(L2-1) 过来的，再执行 1 次插入操作
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
}
}
}
// dp[L1][L2] 表示 word1 的前 L1 个字符转换为 word2 的前 L2 个字符最少操作数
// 把这个结果进行返回
return dp[L1][L2];
}
}
为了帮助大家更好的入门学习算法，我录制了《剑指 Offer》系列的三十道题目，结合动画的形式录制了视频，相信能帮助你更好的刷题。