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’)

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

---

做题思路

这个题目时Hard类型的,我第一遍看完题目后真实是一脸懵哈😄,甚至连需要使用什么方法都没头绪

然后我就默默的点开了官方的题解,看了一下官方的题解,没看太懂,然后翻了一下评论发现一位大神

写的评论非常清楚,看完它的解释,我叭叭的一顿狂写,过了!!!😄

我大概说一下简单的实现思路,只要理解了,实现起来不要太简单~

s1: “abfge”

s2: “zxc”

要将s1 s2 变成一样的字符串,我们可以拆分成三小种情况

• 如果我们知道将 “abfg” 变成 “zxc” 总共需要几步(X),那么我们只需要在删除e即可: X+1
• 如果我们知道将 “zxc” 变成 “abfge” 总共需要几步(Y),那么我们只需要在删除e即可: Y+1
• 如果我们知道将 “zx” 变成 “abfg” 总共需要几步(Z)
  • 如果s1的最后一个字符和s2的最后一个字符一样:那么最终只需要 Z 步
  • 如果s1的最后一个字符和s2的最后一个字符不一样:那么最终只需要 Z +1 步
• 还有一点,如果一个空串"" 变成 一个串 x ,那么需要的步数其实就是 串x的长度
• 好了,以上我认为对于本题核心的部分已经总结出来了,如果你看到这里的话,先不要看我下面的代码实现,自己取力扣上看看能不能做出来

代码实现

class Solution {
  public int minDistance(String word1, String word2) {
    int m=word1.length();
    int n=word2.length();
    int[][] dp=new int[m+1][n+1];
    for(int i=0;i<=m;i++){
      dp[i][0]=i;
    }
    for(int i=0;i<=n;i++){
      dp[0][i]=i;
    }

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

    return dp[m][n];
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

题目链接

72. 编辑距离