首页 > 编程语言 >力扣72-编辑距离(Java详细题解)

力扣72-编辑距离(Java详细题解)

时间:2024-09-22 21:19:08浏览次数:10  
标签:Java 删除 题解 元素 力扣 word1 dp 数组 本题

题目链接:力扣72-编辑距离

前情提要:

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组 利于debug。

每一个dp题目如果都用这五步分析清楚,那么这道题就能解出来了。

题目思路:

如果你做过力扣583-两个字符串的删除操作,或者看过我那篇题解,那么做本题会轻松很多。

本题与力扣583不同的就是,本题可以对单词有三种操作,删除、替换、添加。

而力扣583只有一种操作,就是删除。

本题题目要求使word1转化为word2相同所使用的最少操作数。

使用dp五部曲系统分析一下。

1.确定dp数组和i下标的含义。

dp[i] [j] 是指使i - 1结尾的word1和以j - 1为结尾的word2相同所操作的最少次数。

注意这里是以i - 1为结尾,j - 1为结尾。至于为什么要这样设置dp数组看看我这篇题解力扣718-最长重复子数组(Java详细题解)-CSDN博客

2.确定递推公式。

子序列问题都要考虑word1[i - 1] 是否等于 word2[j - 1]的情况。

  • 相等的情况。

    既然最后结尾的元素相等,那么就要在以前一个为结尾的元素的字符串中操作了。

    所以dp[i] [j] = dp[i - 1] [j - 1];

  • 不相等的情况

    不相等我们就要操作元素了,具体的操作情况有三种。

    1. 删除

    2. 增加

    3. 替换

      其实删除和增加是相互的,你对word1删除使其和word2相同,其实也可以使word2增加使其和word1相同。

      那么肯定有人想我为什么不删然后再加,那么所用的操作数肯定就多了,而且没有意义。

      所以其实这里删除和添加选一个就行了,我这里用的就是删除,具体删除哪个我们不能确定,是由递推公式帮我们确定删除元素多的那个。

      删除的情况就跟力扣583一模一样了就是dp[i] [j] = Math.min(dp[i - 1] [j] + 1,dp[i] [j - 1] + 1);

      替换的话我们就得额外考虑了。

      当我们最后一个元素不相同,需要替换,我们肯定是替换其中的一个使其与另一个相同。所以dp[i] [j] = dp[i - 1] [j - 1] + 1;

      因为我们替换最后一个元素,所以只需要在前一个元素的最少操作数加一即可。

      综上所述:

      dp[i] [j] = Math.min(dp[i - 1] [i - 1] + 1,Math.min(dp[i - 1] [j],dp[i] [j - 1]));

3.dp初始化。

由递推公式可以看出dp[i] [j] 是由dp[i] [j - 1]或者dp[i - 1] [j]或dp[i - 1] [j - 1]推出。

所以在二维dp数组里就由他的上方左方和左上方三个方向推出。

那么起始位置就是第一行和第一列;

dp[i] [0] dp[0] [j] 指的是空串和另一个字符串相同时操作的最少次数。

那么使他们相同的最少操作次数就是让有元素的字符串的元素全部删掉。

所以dp初始化为

for(int i = 0;i <= s.length();i ++){
            dp[i][0] = i;
        }
        for(int i = 0;i <= t.length();i ++){
            dp[0][i] = i;
        }

4.确定dp的遍历顺序。

由递推公式可以看出dp[i] [j] 是由dp[i] [j - 1]或者dp[i - 1] [j]或dp[i - 1] [j - 1]推出。

所以在二维dp数组里就由他的上方左方和左上方三个方向推出。

所以遍历顺序一定是从左到右,从上到下。

5.如果没有ac打印dp数组 利于debug。

在这里插入图片描述

其实前面的题都是用来铺垫本题,如果前面题理解了,那么做本题不会很难。

这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。

我很乐意为你解答。那么我们下篇再见!

标签:Java,删除,题解,元素,力扣,word1,dp,数组,本题
From: https://blog.csdn.net/2302_79761426/article/details/142444273

相关文章

  • java实现角色及菜单权限
    在Java中实现角色及菜单权限管理是一种常见的需求,特别是在企业级应用中。这种权限管理通常涉及多个层次的设计,包括角色、用户、权限和菜单等。下面是一个完整的示例,展示如何在Java中实现角色及菜单权限管理。设计思路实体类定义:定义用户、角色、权限和菜单的实体类。数据库表设计......
  • springboot+java大学周边房屋出租管理系统
    目录项目介绍技术栈具体实现截图开发核心技术:开发工具和技术详细视频演示核心代码部分展示系统设计操作可行性可行性论证系统测试个人心得详细视频演示源码获取方式项目介绍本javaweb+maven项目采用的数据库是Mysql,使用Springboot框架开发,十分方便,也具有跨平台的优......
  • ABC372 F 题解
    F-TeleportingTakahashi2先把问题转化一下:把环断开成链,复制\((K+1)\)层,每走一步就相当于前进一层:可以想到一个简单的dp:设\(f(i,j)\)表示走到第\(i\)层第\(j\)个位置的方案数。初始化:\(f(0,1)=1\),其它均为\(0\),表示Takahashi从第\(0\)层的\(1\)位置......
  • EmployeeTest/EmployeeTest.java
    Employee.javaimportjava.time.LocalDate;publicclassEmployee{//3个字段,用来存放将要操作的数据privateStringname;privatedoublesalary;privateLocalDatehireDay;//通过Generate...生成后修改publicEmployee(Stringname,doub......
  • Java-数据结构-排序-(二) (๑¯∀¯๑)
    文本目录:❄️一、交换排序:    ➷ 1、冒泡排序:    ▶代码:     ➷ 2、快速排序:          ☞基本思想:          ☞方法一:Hoare法    ▶代码:           ☞方法二:挖坑法  ......
  • springboot-ssm-java企业客户关系满意度评价管理系统 o1iv4
    目录项目介绍技术栈具体实现截图开发核心技术:开发工具和技术详细视频演示核心代码部分展示系统设计操作可行性可行性论证系统测试个人心得详细视频演示源码获取方式项目介绍本javaweb+maven项目采用的数据库是Mysql,使用Springboot框架开发,十分方便,也具有跨平台的优......
  • 【JavaSE】Java注解
    什么是注解         我们最早使用的注解有:方法重写@Override,在编译期间进行硬性检测,加在方法上就表明该方法是从父类重写过来的。        Java注解(Annotation)又称Java标注,它可以用来对类、方法、属性、参数、包等进行标注,然后让编译器或运行时其他类进......
  • Java 方法传参机制
    普通变量传参在Java中,一个方法可以选择需要参数或者无需参数,当方法需要参数时,传入参数都发生了什么变化是一个非常值得研究的问题,由此而来,我已自己所学来简单讲解一下其中的机制。实例1这是一个交换两个数值的方法,方法传入了两个形参a和b,交换之后并打印出来。class......
  • 基于Java Springboot 超市云购物系统
    一、作品包含源码+数据库+设计文档万字+全套环境和工具资源+部署教程二、项目技术前端技术:Html、Css、Js、Vue3、Element-ui数据库:MySQL后端技术:Java、SpringBoot、MyBatis三、运行环境开发工具:IDEA数据库:MySQL8.0数据库管理工具:Navicat10以上版本环境配置软件:JDK......
  • 基于Java Springboot 共享单车管理系统
    一、作品包含源码+数据库+设计文档万字+PPT+全套环境和工具资源+部署教程二、项目技术前端技术:Html、Css、Js、Vue3、Element-ui数据库:MySQL后端技术:Java、SpringBoot、MyBatis三、运行环境开发工具:IDEA数据库:MySQL8.0数据库管理工具:Navicat10以上版本环境配置软件......