跳转至

72. 编辑距离

这是六则或许对你有些许帮助的信息:

⭐️1、阿秀与朋友合作开发了一个编程资源网站，目前已经收录了很多不错的学习资源和黑科技（附带下载地址），如过你想要寻求合适的编程资源，欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份阿秀从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解 如果可以的话求个B站三连，感谢！

3、😊 分享一个阿秀自己私藏的黑科技网站，点此直达，主要是各类小众实用APP、网站等，除此外也包括高清影视、音乐、电视剧、AI、纪录片、英语四六级考试、考研考公、副业等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23/24/25届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。

72. 编辑距离 非常经典的DP问题

力扣原题链接（点我直达）

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

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

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

Text Only
1
2
3
4
5
6
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

Text Only
1
2
3
4
5
6
7
8
输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

第一版，别人的解法

第一种解答

求解编辑距离，也是经典老题，编辑距离其实在实际工作中也会用到，主要用于分析两个单词的相似程度，两个单词的编辑距离越小证明两个单词的相似度越高。

题目说可以通过增加字符，删除字符，以及 替换字符 这三个操作来改变一个字符串，并且每个操作的 cost 都是 1，问一个单词转换成另一个单词的最小 cost，老样子，四个步骤分析一遍：

  • 问题拆解

我们考虑求解 str1(0…m) 通过多少 cost 变成 str2(0…n)，还是来看看它的子问题，其实还是三个

  • str1(0…m-1) 通过多少 cost 变成 str2(0…n)

  • str1(0…m) 通过多少 cost 变成 str2(0…n-1)

  • str1(0…m-1) 通过多少 cost 变成 str2(0…n-1)

你可能会问你怎么这么快就写出子问题来，这些子问题是如何推导来的，它们和当前问题之间的联系又是什么？

别急，听我慢慢道来。

一般字符匹配类问题的核心永远是两个字符串中的字符的比较，而且字符比较也只会有两种结果，那就是 相等 和 不相等，在字符比较的结果之上我们才会进行动态规划的统计和推导。

回到这道题，当我们在比较 str1(m) 和 str2(n) 的时候也会有两种结果，即 相等 或不相等，如果说是 相等，那其实我们就不需要考虑这两个字符，问题就直接变成了子问题 str1(0…m-1) 通过多少 cost 变成 str2(0…n-1)，如果说 不相等，那我们就可以执行题目给定的三种变换策略:

  • 将问题中的 str1 末尾字符 str1(m) 删除，因此只需要考虑子问题 str1(0…m-1)，str2(0…n)

  • 将问题中的 str1 末尾字符 str1(m) 替换 成 str2(n)，这里我们就只需要考虑子问题 str1(0…m-1)，str2(0…n-1)

  • 将问题中的 str1 末尾 添加 一个字符 str2(n)，添加后 str1(m+1) 必定等于 str2(n)，所以，我们就只需要考虑子问题 str1(0…m)，str2(0…n-1)

如果你还不是特别清楚问题之间的关系，那就画图表吧，这里我就略过。

  • 状态定义

dp[i][j] 表示的是子问题 str1(0…i)，str2(0…j) 的答案，和常规的字符匹配类动态规划题目一样，没什么特别

  • 递推方程

问题拆解那里其实说的比较清楚了，这里需要把之前的描述写成表达式的形式：

Text Only
1
2
3
4
5
6
7
str1(i) == str2(j):
dp[i][j] = dp[i - 1][j - 1]
tip: 这里不需要考虑 dp[i - 1][j] 以及 dp[i][j - 1]，
因为dp[i - 1][j - 1] <= dp[i - 1][j] +1 && dp[i - 1][j - 1] <= dp[i][j - 1] + 1

str1(i) != str2(j):
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][i - 1]) + 1

你可以看到字符之间比较的结果永远是递推的前提

  • 实现

这里有一个初始化，就是当一个字符串是空串的时候，转化只能通过添加元素或是删除元素来达成，那这里状态数组中存的值其实是和非空字符串的字符数量保持一致。

第二种个解答

  • 问题1：如果 word1[0..i-1] 到 word2[0..j-1] 的变换需要消耗 k 步，那 word1[0..i] 到 word2[0..j] 的变换需要几步呢？
  • 答：先使用 k 步，把 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[0..i] 到 word2[0..j] 的变换需要消耗几步呢？
  • 答：先经过 k 步，把 word1[0..i-1] 变换到 word2[0..j]，消耗掉 k 步，再把 word1[i] 删除，这样，word1[0..i] 就完全变成了 word2[0..j] 了。一共 k + 1 步。
  • 问题3：如果 word1[0..i] 到 word2[0..j-1] 的变换需要消耗 k 步，那 word1[0..i] 到 word2[0..j] 的变换需要消耗几步呢？
  • 答：先经过 k 步，把 word1[0..i] 变换成 word2[0..j-1]，消耗掉 k 步，接下来，再插入一个字符 word2[j], word1[0..i] 就完全变成了 word2[0..j] 了。

从上面三个问题来看，word1[0..i] 变换成 word2[0..j] 主要有三种手段，用哪个消耗少，就用哪个。

执行用时 :16 ms, 在所有 cpp 提交中击败了72.64%的用户

内存消耗 :11.5 MB, 在所有 cpp 提交中击败了7.47%的用户

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
    int minDistance(string word1, string word2) {
    int len1 = word1.size(), len2 = word2.size();
    vector<vector<int>> dp(len1+1,vector<int>(len2+1));
    dp[0][0] = 0;
    for (int i = 1; i <= len1; ++i) {
        dp[i][0] = i;
    }

    for (int j = 1; j <= len2; ++j) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else {
                dp[i][j] = min(dp[i - 1][j],
                    min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            }
        }
    }

    return dp[len1][len2];
    }

第二版，改进一下

执行用时 :12 ms, 在所有 cpp 提交中击败了90.55%的用户

内存消耗 :11.2 MB, 在所有 cpp 提交中击败了41.63%的用户

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int minDistance(string word1, string word2) {
    int len1 = word1.size(), len2 = word2.size();

    vector<vector<int>> dp(len1+1,vector<int>(len2+1));

    for (int i = 0; i <= len1; ++i) {
        for (int j = 0; j <= len2; ++j) {

            if (j == 0) dp[i][0] = i; //从无到有显然要经历i步插入操作
            else if (i == 0) dp[0][j] = j;  //从有到无显然要经历j步删除操作
            else if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else {
                dp[i][j] = min(dp[i - 1][j],
                    min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            }
        }
    }

    return dp[len1][len2];

}