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

这篇具有很好参考价值的文章主要介绍了代码训练LeetCode(6)编辑距离。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

漫漫长路,才刚刚开始…

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

参考文章:

  • 72. 编辑距离 - 力扣(LeetCode)
  • 力扣 (LeetCode) 全球极客挚爱的技术成长平台
1. 原题

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

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

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

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

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
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(如果不相等)))

不断递归迭代下去,我们只要确定边界条件,则可按照递推关系求解任意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) 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 函数用于计算并返回编辑距离。
  • len1len2 分别是两个输入单词的长度。
  • dp 是一个二维数组,用于存储到当前位置为止的最小编辑距离。
  • 初始化 dp 数组的第一行和第一列,这表示一个字符串转换成空字符串所需的步骤数。
  • 接下来的双层 for 循环用于填充 dp 数组的剩余部分。
  • 我们使用嵌套的三元运算符来找到插入、删除和替换操作中的最小值。
  • 函数最后返回 dp[len1][len2],即将 word1 转换为 word2 所需的最小操作数。

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

代码训练LeetCode(6)编辑距离,CS小白之路,#  十年代码训练,# C语言,leetcode,算法,c语言

4. 总结

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

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

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






代码训练LeetCode(6)编辑距离,CS小白之路,#  十年代码训练,# C语言,leetcode,算法,c语言

Once Day

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

如果这篇文章为您带来了帮助或启发,不妨点个赞👍和关注,再加上一个小小的收藏⭐!

(。◕‿◕。)感谢您的阅读与支持~~~文章来源地址https://www.toymoban.com/news/detail-838911.html

到了这里,关于代码训练LeetCode(6)编辑距离的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录第五十六天——两个字符串的删除操作,编辑距离

    题目链接:两个字符串的删除操作 两个字符串可以相互删除 版本一: 确定dp数组及下标的含义 dp[i][j] :以i-1为结尾的字符串word1,和以j-1为结尾的字符串word2,想要达到相等,所需要删除元素的最少次数 确定递推公式 (1)当word1[i - 1] 与 word2[j - 1]相同: (2)当word1[i - 1] 与

    2024年02月02日
    浏览(36)
  • 代码随想录打卡第56天|583. 两个字符串的删除操作;72. 编辑距离

    583. 两个字符串的删除操作 关键点1:dp数组的含义 dp[i][j],使得以i-1为结尾word1 和 以j-1为结尾的word2 相同所需的最小步数; 关键点2:递归公式的推导 if(nums1[i-1] == nums2[j-1]),则i和j同时移动,所以为i-1,j-1;dp[i][j] = dp[i-1][j-1];由于不需要进行删除操作,所以不需要加1 如果不相

    2023年04月19日
    浏览(48)
  • 代码训练LeetCode(14)整数反转

    代码训练(14)LeetCode之整数反转 Author: Once Day Date: 2024年4月9日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 190. 颠倒二进制位 - 力扣(LeetCode) 7. 整数反转 - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题

    2024年04月27日
    浏览(27)
  • 代码训练LeetCode(15)买卖股票

    代码训练(15)LeetCode之买卖股票 Author: Once Day Date: 2024年4月22日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 122. 买卖股票的最佳时机 II - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题 给你一个整数数组

    2024年04月27日
    浏览(24)
  • 代码训练LeetCode(5)最长连续序列

    代码训练(5)LeetCode之最长连续序列 Author: Once Day Date: 2024年3月9日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 128. 最长连续序列 - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题 给定一个未排序的整数数组

    2024年03月24日
    浏览(37)
  • 代码训练LeetCode(12)二进制求和

    Author: Once Day Date: 2024年3月14日 一位热衷于Linux学习和开发的菜鸟,试图谱写一场冒险之旅,也许终点只是一场白日梦… 漫漫长路,有人对你微笑过嘛… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 67. 二进制求和 - 力扣(LeetCode) 力扣 (LeetCode) 全球极

    2024年03月20日
    浏览(46)
  • 代码训练LeetCode(2)区间列表的交集

    代码训练(2)LeetCode之区间列表的交集 Author: Once Day Date: 2024年3月5日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 986. 区间列表的交集 - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 问题 给定两个由一些 闭区间

    2024年03月12日
    浏览(35)
  • 代码训练LeetCode(13)颠倒二进制位

    代码训练(13)LeetCode之颠倒二进制位 Author: Once Day Date: 2024年4月9日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 190. 颠倒二进制位 - 力扣(LeetCode) 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 原题 颠倒给定的 32 位无符号整

    2024年04月27日
    浏览(44)
  • 代码训练LeetCode(9)Git自动同步脚本

    代码训练(9)LeetCode之Git自动同步脚本 Author: Once Day Date: 2024年3月10日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: Git使用记录_Once-Day的博客-CSDN博客 1. 题目 这个题目是自拟的,来自于个人开发过程中的需求: 写段bash脚本,同步

    2024年03月17日
    浏览(44)
  • CS420 课程笔记 P5 - 内存编辑 & 数据类型

    这节课将结束数据类型并涵盖更高级的 game hacking 技巧,特别是学习如何编辑我们看不到的数字,例如玩家的 XYZ 坐标或者没有显示数字的血条,这被称为 未知值扫描 ,因此数据类型只是计算机上存储信息的方式,我们已经学到了很多比如 ASCII 和 Unicode,当然我们还有负数和

    2024年02月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包