代码训练(6)LeetCode之编辑距离
Author: Once Day Date: 2024年3月9日
漫漫长路,才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
- 72. 编辑距离 - 力扣(LeetCode)
- 力扣 (LeetCode) 全球极客挚爱的技术成长平台
1. 原题
给你两个单词
word1
和word2
, 请返回将word1
转换成word2
所使用的最少操作数 。你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
例如对于horse
和ros
两个单词,其最少操作数为3,即如下三步:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
2. 分析
这种表面一看,似乎是个字符串问题,但是如果按照分类匹配去做,怕是很难得出合理的方法。求两个字符串的编辑距离实际是个动态规划入门题目,动态规划算法是解决这个问题的标准方法。
我们先从逻辑分析一下,对于两个字符串,如horse
和ros
,在三种操作下,其最小操作数有下述四种情况:
- 已知字符串
hors
和ros
的最小操作数,然后再删除一个字母e
,即:MinOperation["hors"]["ros"] + 1
。 - 已知字符串
horse
和ro
的最小操作数,然后再增加一个字母s
,即:MinOperation["horse"]["ro"] + 1
。 - 已知字符串
hors
和ro
的最小操作数,然后再替换一个字母e -> s
,即:MinOperation["hors"]["ro"] + 1
。 - 已知字符串
hors
和ros
的最小操作数,如果最后一个字母相同,则不变,即:MinOperation["hors"]["ros"]
。
第四种情况为特殊情况,即无需替换,通过上面分类讨论思想,可以发现,MinOperation["horse"]["ros"]
取决于其单词前面字符的最小操作,这点很好理解,因为最后一个操作,一定是上述四种操作之一。
我们用i
代表horse
前i
个字符组成的子字符串,j
代表ros
前j
个字符组成的子字符串,则存在下述表达式:
MinOperation[i][j] = Min(
(MinOperation[i-1][j] + 1),
(MinOperation[i][j-1] + 1),
(MinOperation[i-1][j-1] + 1(如果不相等)))
不断递归迭代下去,我们只要确定边界条件,则可按照递推关系求解任意i
和j
值的最小操作数,如下:
- 当
i = 0
时,即MinOperation[0][j] = j
,因为word1是空字符串,直接增加j
个字符后变成word2。 - 当
j = 0
时,即MinOperation[i][0] = i
,因为word2是空字符串,直接删除i
个字符后变成word2。 - 当
i = j = 0
时,即MinOperation[0][0] = 0
,都是空字符串。
下面创建一个二维数组 dp
,其中 dp[i][j]
表示从 word1
的前 i
个字符转换到 word2
的前 j
个字符所需要的最小操作数。
- 初始化边界条件:
dp[i][0]
和dp[0][j]
分别表示将word1
的前i
个字符全部删除和将word2
的前j
个字符全部插入到word1
。 - 遍历
word1
和word2
的每个字符:- 如果当前字符相同,则
dp[i][j] = dp[i-1][j-1]
。 - 如果字符不同,我们需要考虑三种情况:
- 插入一个字符:
dp[i][j] = dp[i][j-1] + 1
- 删除一个字符:
dp[i][j] = dp[i-1][j] + 1
- 替换一个字符:
dp[i][j] = dp[i-1][j-1] + 1
- 插入一个字符:
- 我们取这三种情况的最小值作为
dp[i][j]
的结果。
- 如果当前字符相同,则
- 最后
dp[length(word1)][length(word2)]
就是我们要找的答案。
按照这个算法我们可以逐步算出不同i
和j
值的最小操作数,如下表所示:
(1) 首先构建初始化边界条件,即i
和j
都为0的情况。
MinOperation | (空字符串0) | 字符1r
|
字符2o
|
字符3s
|
---|---|---|---|---|
(空字符串0) | 0 | 1 | 2 | 3 |
字符1h
|
1 | |||
字符2o
|
2 | |||
字符3r
|
3 | |||
字符4s
|
4 | |||
字符5e
|
5 |
(2) 然后我们可以按照从左到右,从上到下,依次遍历整个表格,直到填满整个表格。
MinOperation | (空字符串0) | 字符1r
|
字符2o
|
字符3s
|
---|---|---|---|---|
(空字符串0) | 0 | 1 | 2 | 3 |
字符1h
|
1 | 1(替换h) | 2 | 3 |
字符2o
|
2 | 2 | 1(o相等) | 2 |
字符3r
|
3 | 2 | 2(删除r) | 2 |
字符4s
|
4 | 3 | 3 | 2(s相等) |
字符5e
|
5 | 4 | 4 | 3(删除e) |
通过上表可以看出来,依次遍历整张表格的流程,也就揭示了操作的流程。
本次问题的性能优化关键点如下:
-
空间优化:如果我们只关心最终的编辑距离,不需要回溯操作路径,则可以只保留
dp
数组的两行来节省空间。 - 代码优化:确保循环和逻辑判断尽可能简洁,避免不必要的计算。
3. 代码实现
int minDistance(char * word1, char * word2){
int len1 = strlen(word1);
int len2 = strlen(word2);
int dp[len1 + 1][len2 + 1];
if (len1 == 0) {
return len2;
}
if (len2 == 0) {
return len1;
}
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; 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] = 1 + (dp[i - 1][j - 1] < dp[i][j - 1] ?
(dp[i - 1][j - 1] < dp[i - 1][j] ? dp[i - 1][j - 1] : dp[i - 1][j]) :
(dp[i][j - 1] < dp[i - 1][j]? dp[i][j - 1] : dp[i - 1][j]));
}
}
}
return dp[len1][len2];
}
上面的 C 语言代码实现了编辑距离算法:
-
minDistance
函数用于计算并返回编辑距离。 -
len1
和len2
分别是两个输入单词的长度。 -
dp
是一个二维数组,用于存储到当前位置为止的最小编辑距离。 - 初始化
dp
数组的第一行和第一列,这表示一个字符串转换成空字符串所需的步骤数。 - 接下来的双层
for
循环用于填充dp
数组的剩余部分。 - 我们使用嵌套的三元运算符来找到插入、删除和替换操作中的最小值。
- 函数最后返回
dp[len1][len2]
,即将word1
转换为word2
所需的最小操作数。
下面是运行结果图(数据仅供参考,不具备实际意义):
4. 总结
本题主要考察了动态规划的理解和应用能力。动态规划是一个非常强大的工具,它可以解决许多看似复杂的问题,将问题分解成一系列子问题,并且保证每个子问题只解决一次,保存其解以避免重复计算。
要提高解决这类问题的能力,我们应该:
- 理解动态规划的基本概念,如状态转移方程、边界条件等。
- 练习各种不同类型的动态规划问题,从简单到复杂逐渐提升。
- 学会如何将问题分解为子问题,并识别出子问题之间的依赖关系。
的问题,将问题分解成一系列子问题,并且保证每个子问题只解决一次,保存其解以避免重复计算。
Once Day
也信美人终作土,不堪幽梦太匆匆......
如果这篇文章为您带来了帮助或启发,不妨点个赞👍和关注,再加上一个小小的收藏⭐!文章来源:https://www.toymoban.com/news/detail-838911.html
(。◕‿◕。)感谢您的阅读与支持~~~文章来源地址https://www.toymoban.com/news/detail-838911.html
到了这里,关于代码训练LeetCode(6)编辑距离的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!