代码随想录 Day47 动态规划15 LeetCode T583 两个字符串的删除操作 T72 编辑距离

LeetCode T583 两个字符串的删除操作

题目链接:583. 两个字符串的删除操作 - 力扣(LeetCode)

题目思路:

本题有两个思路

1.使用两个字符串的长度之和-2*最长公共子串(换汤不换药)

代码随想录Day45 动态规划13 LeetCode T1143最长公共子序列 T1135 不相交的线 T53最大子数组和-CSDN博客

2.使用不同子序列的思路,从只能删除母串到现在的两个字符串可以相互修改

这里我介绍第二种思路,第一种思路在之前已经介绍过,可以查看我的

1.明确dp数组含义

这里的dp数组含义就是以i-1结尾的字符串word1和以j-1为结尾的字符串word2,要想达到相等,所需的最小次数.

2.明确递推公式

分为相等和不相等两种情况

2.1 相等 

dp[i][j] = dp[i-1][j-1] 延续这种状态,因为相同无需删除

2.2 不相等

dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j+1],dp[i-1][j-1]+2)

需要删除,这里就选择删除word1的尾字母,删除word2的尾字母或者删除word1和word2的尾字母,求最小值即可

3.初始化dp数组

将dp[i][0] 初始化为i,因为这里word2没有字母,想要相同只能删除word1的全部字母

同理,dp[0][j]初始化为j即可

4.明确遍历顺序

从前向后遍历,因为后面的数据要依托与前面的数据而产生

5.打印dp数组排错

题目代码:

1.最长公共子串法
class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1+1][len2+1];
        for(int i = 1;i<=len1;i++){
            char c1= word1.charAt(i-1);
            for(int j = 1;j<=len2;j++){
                char c2 = word2.charAt(j-1);
                if(c1 == c2){
                    dp[i][j] =  dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return len1+len2-2*dp[len1][len2];

    }
}

2.删除法
class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1+1][len2+1];
        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++){
            char c1= word1.charAt(i-1);
            for(int j = 1;j<=len2;j++){
                char c2 = word2.charAt(j-1);
                if(c1 == c2){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+2));
                }
            }
        }
        return dp[len1][len2];

    }
}

LeetCode T72 编辑距离

题目链接:72. 编辑距离 - 力扣(LeetCode)

题目思路:

仍然是使用动规五部曲来解决

1.确定dp数组含义

dp[i][j]的含义仍然是以i-1结尾的word1和j-1结尾的word2的最近编辑距离

2.确定递推公式

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

其实这里的增和删是一样的,比如word1是'ab',word2是'a'

这里我们可以用word1删除一个b或者用word2添加一个b,都是可以的,所以我们考虑以中国情况即可

2.1 相同的情况

如果c1 == c2

那么是不是无需操作直接延续前一次的dp[i-1][j-1]都可以

即dp[i][j] = dp[i-1][j-1];

2.2 不同的情况

这里就要考虑增删改了,其实也可以说是删改即可

能到达dp的就有dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1(相同直接延续,不同修改一个变成另一个即可)我们在三者之间取最小值即可

3.初始化dp数组

因为dp[i][j]依赖于前面产生,所以我们初始化dp[i][0]和dp[0][j]即可

dp[i][0]其实就是表示i到空字符串需要多少步,当然是i步

同理dp[0][j] = j

4.遍历顺序

从前向后遍历,因为后面的数据依赖前面的数据产生

5.打印dp数组排错

假设word1 = horse

        word2 = ros dp数组如下

题目代码:

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1+1][len2+1];
        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++){
            char c1 = word1.charAt(i-1);
            for(int j = 1;j<=len2;j++){
                char c2 = word2.charAt(j-1);
                if(c1 == c2){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }
            }
        }
        return dp[len1][len2];

    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/152456.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

kubectl 本地远程链接k8s多个集群,远程管控多集群,查看日志 部署服务(windows版)

文章目录 一、前言二、windows上安装kubectl和mobaxterm2.1 准备安装包2.2 安装kubectl2.3 链接k8s集群2.4 查看某一个pod的容器日志2.5 切换context 上下文配置&#xff0c;实现在多个k8s集群间动态切换 一、前言 现如今是一个万物皆上云 的时代&#xff0c;各种云层出不穷&am…

JEECG BOOT 前端记录

目录 查询 1、模糊搜索中文 2、下拉框选择 3、文本框 新增 1、添加文本框 2、图片上传 3、文件上传 4、富文本 5、下拉框数字回显文字 第一种&#xff1a; 第二种&#xff1a; 展示 1、字典翻译注解Dict 1.2、字典表翻译用法 2、点击事件调接口 查询 1、模糊搜索中…

新生儿腿纹不对称:原因、科普和注意事项

引言&#xff1a; 新生儿身上出现腿纹不对称的现象在一些家庭中可能引起担忧&#xff0c;然而&#xff0c;了解这一现象的原因以及如何正确处理是非常重要的。本文将科普新生儿腿纹不对称的原因&#xff0c;提供相关信息&#xff0c;并为父母和监护人提供注意事项&#xff0c;…

腾讯待办是什么?关停之后如何继续提醒待办事项?

由于业务方向调整&#xff0c;腾讯待办将于2023年的12月20日全面停止运营并下架。那么腾讯待办是什么呢&#xff1f;它是一款以微信小程序呈现的待办事项和日程管理工具&#xff0c;旨在帮助用户更好地管理自己的待办事项和日程安排。用户可以在该小程序中创建待办事项、设置提…

单词故事嵌入:通过自然语言处理解开叙事

一、介绍 在自然语言处理和文本分析领域&#xff0c;寻求理解和表示人类叙事丰富而复杂的结构是一个持续的挑战。在研究人员和数据科学家可以使用的众多工具和技术中&#xff0c;“Word Story Embeddings”作为一种创新且有前景的方法脱颖而出。这些嵌入建立在词嵌入的基础上&a…

力扣每日一题-最长奇偶子数组-2023.11.16

力扣每日一题&#xff1a;最长奇偶子数组 题目链接:2760.最长奇偶子数组 题目描述 代码思路 利用单指针进行扫描&#xff0c;符合子数组起点要求时&#xff0c;开始记录子数组长度。题目本身不难理解&#xff0c;就是判断的条件比较多&#xff0c;需要耐心和细心。 代码纯享…

进程终止和进程等待

一 进程终止 (1)exit和return 先前已经了解了进程创建&#xff0c;以及进程大致相关的数据结构&#xff0c;但是有个小知识一直没提及&#xff0c;那就是exit&#xff0c;还有就是return 0。这两个的作用有点相似&#xff0c;都可以终止进程&#xff0c;但又有点不同&#xff…

Hoppscotch:开源 API 开发工具,快捷实用 | 开源日报 No.77

hoppscotch/hoppscotch Stars: 56.1k License: MIT Hoppscotch 是一个开源的 API 开发生态系统&#xff0c;主要功能包括发送请求和获取实时响应。该项目具有以下核心优势&#xff1a; 轻量级&#xff1a;采用简约的 UI 设计。快速&#xff1a;实时发送请求并获得响应。支持多…

【开源】基于Vue和SpringBoot的网上药店系统

项目编号&#xff1a; S 062 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S062&#xff0c;文末获取源码。} 项目编号&#xff1a;S062&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 药品类型模块2.3 药…

前后端联调时JS数据精度问题的解决

在JavaScript中&#xff0c;Number类型范围 -2^53 1 到 2^53 - 1&#xff0c;而在Java中Long类型的取值范围是 -2^63 1 到 2^63 - 1, 比JavaScript中大很多&#xff0c;所以后端能正常处理。 其实 ES6 引入了 Number.MAX_SAFE_INTEGER 和 Number.MIN_SAFE_INTEGER 这两个常量…

【wvp+ GiVideoCall】 三种主要应用场景

目录 点播场景 聊天室场景 双人视频 点播场景 主动对象&#xff1a; 视频调度平台。 被点播对象&#xff1a; 登录平台的web用户&#xff0c;android用户&#xff1b;国标设备。 功能&#xff1a; 视频点播&#xff1b;伴音&#xff1b;对讲&#xff1b;录相&#xff1b; 聊…

RabbitMQ 安装及配置

前言 当你准备构建一个分布式系统、微服务架构或者需要处理大量异步消息的应用程序时&#xff0c;消息队列就成为了一个不可或缺的组件。而RabbitMQ作为一个功能强大的开源消息代理软件&#xff0c;提供了可靠的消息传递机制和灵活的集成能力&#xff0c;因此备受开发人员和系…

基于Springboot的非物质文化网站(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的非物质文化网站&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 项目介…

耿明雨出席柬方70周年招待会晚宴

11月9日&#xff0c;庆祝柬埔寨独立和建军70周年欢迎晚宴上&#xff0c;全国政协副主席沈跃跃盛邀出席&#xff0c;此次招待会是由柬埔寨王国驻华大使馆主办&#xff0c;在北京励骏酒店圆满召开&#xff0c;晚宴现场&#xff1b;凯西索达大使致辞、中国外交部部长助理徐飞洪等领…

亓长东、王喜成莅临科大讯飞,共谋科技与服装行业的深度融合

近日&#xff0c;国务院发展研究中心研究员、经济学博士亓长东&#xff0c;雷蒙服饰有限公司董事长王喜成一行莅临科大讯飞进行调研。科大讯飞副总裁张友国热情陪同&#xff0c;双方就科技与服装行业的深度融合进行了深入交流。 在科大讯飞副总裁张友国的陪同下&#xff0c;亓长…

解决Qt5.13.0无MySQL驱动问题

一、前言 由于Qt5.12.3是最后提供mysql数据库插件的版本&#xff0c;往后的版本需要自行编译对应的mysql数据库插件&#xff0c;官方安装包不再提供。使用高版本的Qt就需要自行编译mysql驱动。 若没有编译在QT中调用Qsqldatabase库连接mysql时&#xff0c;提示出现如下问题&a…

Windows系统下使用tar命令,压缩文件与解压缩文件并指定路径

如果想指定解压缩后的文件夹&#xff0c;请看第三步 第一步&#xff1a;进入解压文件所在的当前文件夹内右键点击在终端打开 如下图 第二步&#xff1a;在终端内输入命令行&#xff08;分为两种情况&#xff09; 此步骤分为两种情况 2.1 情况一{文件后缀为.tar.gz} ## x…

VirtualKD-Redux 双机调试内驱驱动

官网使用说明 官网下载地址 简单的说 1. 如果是64位虚拟机&#xff0c;把target64文件夹拷贝到虚拟机中&#xff0c;然后安装vminstall.exe 2. 我电脑是用windbg prview, 在主机上打开 vmmon64.exe 3 设置DbgX.Shell.exe路径 D:\安装\WinDbg Preview1.1910.3003.0\Microsoft…

C++进阶-STL 常用算法列举

STL 常用算法列举 概述常用遍历算法for_each 遍历容器transfrom 搬运容器到另一个容器中 常用查找函数find 查找元素find_if 按条件查找元素adjacent_find 查找相邻重复元素binary_search 二分查找法count 统计元素个数count_if 按条件统计元素个数 常用排序算法sort 对元素内内…

Java获取Jar、War包路径,并生成可编辑修改的本地配置文件

前言 本地的可修改配置文件的编写理应是一个很常用的功能&#xff0c;但由于数据库的存在&#xff0c;它鲜少被提及&#xff0c;大多数我们直接存储到数据库中了。 以至于现今&#xff0c;除了没接触数据库的新手时常使用它以外&#xff0c;它没有太多的出场机会。 也因此&am…