当前位置:   article > 正文

代码训练LeetCode(6)编辑距离_编辑距离c语言,只考虑插入

编辑距离c语言,只考虑插入

代码训练(6)LeetCode之编辑距离

Author: Once Day Date: 2024年3月9日

漫漫长路,才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

1. 原题

给你两个单词 word1word2请返回将 word1 转换成 word2 所使用的最少操作数

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

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

例如对于horseros两个单词,其最少操作数为3,即如下三步:

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
  • 1
  • 2
  • 3
2. 分析

这种表面一看,似乎是个字符串问题,但是如果按照分类匹配去做,怕是很难得出合理的方法。求两个字符串的编辑距离实际是个动态规划入门题目,动态规划算法是解决这个问题的标准方法。

我们先从逻辑分析一下,对于两个字符串,如horseros,在三种操作下,其最小操作数有下述四种情况:

  1. 已知字符串horsros的最小操作数,然后再删除一个字母e,即: MinOperation["hors"]["ros"] + 1
  2. 已知字符串horsero的最小操作数,然后再增加一个字母s,即: MinOperation["horse"]["ro"] + 1
  3. 已知字符串horsro的最小操作数,然后再替换一个字母e -> s,即: MinOperation["hors"]["ro"] + 1
  4. 已知字符串horsros的最小操作数,如果最后一个字母相同,则不变,即: MinOperation["hors"]["ros"]

第四种情况为特殊情况,即无需替换,通过上面分类讨论思想,可以发现,MinOperation["horse"]["ros"]取决于其单词前面字符的最小操作,这点很好理解,因为最后一个操作,一定是上述四种操作之一。

我们用i代表horsei个字符组成的子字符串j代表rosj个字符组成的子字符串,则存在下述表达式:

MinOperation[i][j] = Min(
	(MinOperation[i-1][j] + 1), 
	(MinOperation[i][j-1] + 1), 
    (MinOperation[i-1][j-1] + 1(如果不相等)))
  • 1
  • 2
  • 3
  • 4

不断递归迭代下去,我们只要确定边界条件,则可按照递推关系求解任意ij值的最小操作数,如下:

  1. i = 0时,即MinOperation[0][j] = j,因为word1是空字符串,直接增加j个字符后变成word2。
  2. j = 0时,即MinOperation[i][0] = i,因为word2是空字符串,直接删除i个字符后变成word2。
  3. i = j = 0时,即MinOperation[0][0] = 0,都是空字符串。

下面创建一个二维数组 dp,其中 dp[i][j] 表示从 word1 的前 i 个字符转换到 word2 的前 j 个字符所需要的最小操作数。

  1. 初始化边界条件:dp[i][0]dp[0][j] 分别表示将 word1 的前 i 个字符全部删除和将 word2 的前 j 个字符全部插入到 word1
  2. 遍历word1word2的每个字符:
    • 如果当前字符相同,则 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] 的结果。
  3. 最后 dp[length(word1)][length(word2)] 就是我们要找的答案。

按照这个算法我们可以逐步算出不同ij值的最小操作数,如下表所示:

(1) 首先构建初始化边界条件,即ij都为0的情况。

MinOperation(空字符串0)字符1r字符2o字符3s
(空字符串0)0123
字符1h1
字符2o2
字符3r3
字符4s4
字符5e5

(2) 然后我们可以按照从左到右,从上到下,依次遍历整个表格,直到填满整个表格。

MinOperation(空字符串0)字符1r字符2o字符3s
(空字符串0)0123
字符1h11(替换h)23
字符2o221(o相等)2
字符3r322(删除r)2
字符4s4332(s相等)
字符5e5443(删除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];
}
  • 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
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

上面的 C 语言代码实现了编辑距离算法:

  • minDistance 函数用于计算并返回编辑距离。
  • len1len2 分别是两个输入单词的长度。
  • dp 是一个二维数组,用于存储到当前位置为止的最小编辑距离。
  • 初始化 dp 数组的第一行和第一列,这表示一个字符串转换成空字符串所需的步骤数。
  • 接下来的双层 for 循环用于填充 dp 数组的剩余部分。
  • 我们使用嵌套的三元运算符来找到插入、删除和替换操作中的最小值。
  • 函数最后返回 dp[len1][len2],即将 word1 转换为 word2 所需的最小操作数。

下面是运行结果图(数据仅供参考,不具备实际意义):

在这里插入图片描述

4. 总结

本题主要考察了动态规划的理解和应用能力。动态规划是一个非常强大的工具,它可以解决许多看似复杂的问题,将问题分解成一系列子问题,并且保证每个子问题只解决一次,保存其解以避免重复计算。

要提高解决这类问题的能力,我们应该:

  • 理解动态规划的基本概念,如状态转移方程、边界条件等。
  • 练习各种不同类型的动态规划问题,从简单到复杂逐渐提升。
  • 学会如何将问题分解为子问题,并识别出子问题之间的依赖关系。
    的问题,将问题分解成一系列子问题,并且保证每个子问题只解决一次,保存其解以避免重复计算。






Alt

Once Day

也信美人终作土,不堪幽梦太匆匆......

如果这篇文章为您带来了帮助或启发,不妨点个赞

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/621062
推荐阅读
相关标签