当前位置: 首页 > news >正文

算法随想录算法训练营第四十六天| 583. 两个字符串的删除操作 72. 编辑距离

583. 两个字符串的删除操作 

题目:给定两个单词 word1 和 word2 ,返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

思路:这题思路主要是求出 word1 字符串和 word2 字符串中的最长相同的子字符串(比如“abc”子字符串为“a”,“b”,“c”,“ab”,“ac”,“bc”,“abc”);求出最长相同的字符串之后,用两个字符串的长度和减去两倍的最长相同子字符串就是我们需要求得长度。 

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++){for(int j=1;j<=len2;j++){if(word1.charAt(i-1) == word2.charAt(j-1)){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];}
}

72. 编辑距离 

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

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

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
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 i = 0; i <= len2; i++) {dp[0][i] = i;}for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (word1.charAt(i-1) == word2.charAt(j-1))dp[i][j] = dp[i - 1][j - 1];elsedp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;//三种情况,分别代表dp[i][j - 1]:增加一个元素,dp[i - 1][j]:删除一个元素, dp[i - 1][j - 1]修改一个元素}}return dp[len1][len2];}
}

相关文章:

算法随想录算法训练营第四十六天| 583. 两个字符串的删除操作 72. 编辑距离

583. 两个字符串的删除操作 题目&#xff1a;给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 思路&#xff1a;这题思路主要是求出 word1 字符串和 word2 字符串中的最长相同的子字符串&…...

vue源码分析(五)——vue render 函数的使用

文章目录 前言一、render函数1、render函数是什么&#xff1f; 二、render 源码分析1.执行initRender方法2.vm._c 和 vm.$createElement 调用 createElement 方法详解&#xff08;1&#xff09;区别&#xff08;2&#xff09;代码 3、原型上的_render方法&#xff08;1&#xf…...

Maven第三章:IDEA集成与常见问题

Maven第三章:IDEA集成与常见问题 前言 本章内容重点:了解如何将Maven集成到IDE(如IntelliJ IDEA或Eclipse)中,以及使用过程中遇到的常见的问题、如何解决,如何避免等,可以大大提高开发效率。 IEAD导入Maven项目 File ->Open 选择上一章创建的Maven项目 my-app查看po…...

数据结构—线性实习题目(二)5迷宫问题(栈)

迷宫问题&#xff08;栈&#xff09; #include <iostream>​ #include <assert.h> using namespace std;int qi1, qi2; int n; int m1, p1; int** Maze NULL; int** mark NULL;struct items {int x, y, dir; };struct offsets {int a, b;char* dir; };const int…...

Nginx 的配置文件(负载均衡,反向代理)

Nginx可以配置代理多台服务器&#xff0c;当一台服务器宕机之后&#xff0c;仍能保持系统可用。 cmd查找端口是否使用&#xff1a;netstat -ano Nginx出现403 forbidden #解决办法&#xff1a;修改web目录的读写权限&#xff0c;或者是把nginx的启动用户改成目录的所属用户&…...

项目管理49个过程定义与作用、五大过程组

五大过程组&#xff1a; 49个过程的定义与作用&#xff1a; 1.整合管理&#xff1a; (1)制定项目章程&#xff1a;制定项目章程是编写一份正式批准项目并授予项目经理权力的文件的过程&#xff0c;其作用是①确立组织与项目的关系&#xff1b;②展示组织对项目的承诺&#xff…...

MySQL篇---第六篇

系列文章目录 文章目录 系列文章目录一、 MySQL 中 varchar 与 char 的区别?varchar(30) 中的 30代表的涵义?二、 int(11) 中的 11 代表什么涵义?三、为什么 SELECT COUNT(*) FROM table 在 InnoDB 比MyISAM 慢?一、 MySQL 中 varchar 与 char 的区别?varchar(30) 中的 30…...

QA新人入职任务

一、背景 分享记录一下入职新公司后&#xff0c;新人第一周接到的新手任务&#xff0c;回顾总结&#xff0c;方便自己成长和思考~ 二、新人任务说明 题目1&#xff1a;接口相关 题目2&#xff1a;UI相关 UI原型图 三、任务要求 1、根据题目2原型图&#xff0c;进行UI测试…...

更新电脑显卡驱动的操作方法有哪些?

更新显卡驱动可以有效的提升我们电脑的性能&#xff0c;可以通过设备管理器、显卡驱动软件等方式进行检查驱动是否需要更新&#xff0c;并修复一些电脑上已知的显卡问题。 然而&#xff0c;对于一些不是很懂电脑技术的人员来说&#xff0c;更新电脑显卡驱动是一件比较复杂和混乱…...

[Docker]三.Docker 部署nginx,以及映射端口,挂载数据卷

一.Docker 部署 Nginx 以及端口映射 Docker 部署 Nginx,首先需要下载nginx镜像,然后启动这个镜像,就运行了一个nginx的容器了 1.下载 nginx 镜像并启动容器 #查看是否存在nginx镜像:发现没有nginx镜像 [rootlocalhost zph]# docker images | grep nginx#下载nginx镜像 [rootl…...

【0基础学Java第三课】-- 运算符

3. 运算符 3.1 什么是运算符3.2 算术运算符3.2.1 **基本四则运算符&#xff1a;加减乘除模( - * / %&#xff09;**3.2.2 增量运算符 - * %3.2.3 自增/自减运算符 -- 3.3 关系运算符3.4逻辑运算符(重点)3.4.1 逻辑与 &&3.4.2 逻辑 ||3.4.3逻辑非 !3.4.4 短路求值 3.5 …...

unocss和tailwindcss css原子引擎

第一种tailwindcss&#xff1a; tailwindcss官网 https://tailwindcss.com/docs/grid-column 基本介绍及优点分析 Tailwind CSS 中文文档 - 无需离开您的HTML&#xff0c;即可快速建立现代网站 PostCss 处理 Tailwind Css 基本流程 PostCSS - 是一个用 JavaScript 工具和插…...

HIT_OS_LAB1 调试分析 Linux 0.00 引导程序

操作系统实验一 姓名&#xff1a;董帅学号&#xff1a;2021111547班级&#xff1a;21R0312 1.1 实验目的 熟悉实验环境掌握如何手写Bochs虚拟机的配置文件掌握Bochs虚拟机的调试技巧掌握操作系统启动的步骤 1.2 实验内容 1.2.1 掌握如何手写Bochs虚拟机的配置文件 boot: f…...

C语言每日一题(18)数组匹配

牛客网 BC156 牛牛的数组匹配 题目描述 描述 牛牛刚学会数组不久&#xff0c;他拿到两个数组 a 和 b&#xff0c;询问 b 的哪一段连续子数组之和与数组 a 之和最接近。 如果有多个子数组之和同样接近&#xff0c;输出起始点最靠左的数组。 输入描述&#xff1a; 第一行输…...

redroid11 集成 nvidia gpu hals

前言 此篇文章中使用 nvidia 相关aosp 库、510.155_Android_R_aarch64_release文件来于原厂提供基础资料&#xff0c;可供 aosp 移植库基本思路。 本文记录 redroid11(aosp11) 集成 nvidia gpu 驱动库、 nvidia_omx 驱动库实践记录&#xff0c;以作备忘。 1>. Apply the p…...

在 Visual Studio 中远程调试 C++ 项目

目录 一、说明二、下载远程工具1. 官网下载2. 自己电脑上拷贝 三、 运行远程工具四、本机Visual Studio配置五、自动部署 一、说明 参考官方文档&#xff1a;https://learn.microsoft.com/zh-cn/visualstudio/debugger/remote-debugging-cpp?viewvs-2022 二、下载远程工具 …...

AAOS CarMediaService 问题分析

文章目录 问题描述车载蓝牙音乐流程Music 监听焦点变化流程BT请求焦点的流程MediaSession 服务端的流程BT和music 之间的相互影响 问题描述 问题 AAOS界面连接蓝牙的情况下&#xff0c;Music应用播放音乐会暂停。 分析 暂停是应用的行为&#xff0c;Music应用会监听focus的变化…...

06-Flask-蓝图的使用

蓝图的使用 前言蓝图使用方式 前言 本篇来学习下Flask中蓝图的使用 蓝图 在Flask中使用蓝图(Blurprint)来分模块组织管理蓝图可以理解为存储一组视图方法的容器对象&#xff0c;特点如下&#xff1a; 一个应用可以具有多个Blueprint可以将一个Blueprint注册到任何一个未使用…...

【LeetCode力扣】189 53 轮转数组 | 最大子数组和

目录 1、189. 轮转数组 1.1、题目介绍 1.2、解题思路 2、53. 最大子数组和 2.1、题目介绍 2.2、解题思路 1、189. 轮转数组 1.1、题目介绍 原题链接&#xff1a;189. 轮转数组 - 力扣&#xff08;LeetCode&#xff09; ​ 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3输…...

Go学习第十七章——Gin中间件与路由

Go web框架——Gin中间件与路由 1 单独注册中间件1.1 入门案例1.2 多个中间件1.3 中间件拦截响应1.4 中间件放行 2 全局注册中间件3 自定义参数传递4 路由分组4.1 入门案例4.2 路由分组注册中间件4.3 综合使用 5 使用内置的中间件6 中间件案例权限验证耗时统计 1 单独注册中间件…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...