如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

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

力扣原题链接(点我直达) (opens new window)

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

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

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

示例 1:

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

示例 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
2
3
4
5
6
7
8

# 第一版,别人的解法

# 第一种解答

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

题目说可以通过增加字符删除字符,以及 替换字符 这三个操作来改变一个字符串,并且每个操作的 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) 的答案,和常规的字符匹配类动态规划题目一样,没什么特别

  • 递推方程

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

    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
    2
    3
    4
    5
    6
    7

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

  • 实现

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

# 第二种个解答

  • 问题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%的用户

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

# 第二版,改进一下

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

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

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

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24