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

【LeetCode】72. 编辑距离(中等)——代码随想录算法训练营Day55

题目链接:72. 编辑距离

题目描述

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

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

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

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

文章讲解:代码随想录

视频讲解:动态规划终极绝杀! LeetCode:72.编辑距离_哔哩哔哩_bilibili

题解1:动态规划

思路:使用动态规划法求解编辑距离问题。

动态规划分析:

  • dp 数组以及下标的含义:dp[i][j] 代表以 word1[i - 1] 和 word2[j - 1] 结尾的字符串需要进行多少次操作。
  • 递推公式:word1[i - 1] 等于 word2[j - 1] 时,dp[i][j] = dp[i - 1][j - 1];否则,dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1,3个表达式分别对应替换、删除和新增。
  • dp 数组初始化:dp[i][0] = i,dp[0][j] = j。
  • 遍历顺序:从上往下,从左往右。
  • 打印 dp 数组:以输入 word1 = "horse"、word2 = "ros" 为例,dp 数组为 [ [ 0, 1, 2, 3 ], [ 1, 1, 2, 3 ], [ 2, 2, 1, 2 ], [ 3, 2, 2, 2 ], [ 4, 3, 3, 2 ], [ 5, 4, 4, 3 ] ]。
/*** @param {string} word1* @param {string} word2* @return {number}*/
var minDistance = function(word1, word2) {const dp = new Array(word1.length + 1).fill().map(() => new Array(word2.length + 1).fill(0));for (let i = 1; i <= word1.length; i++) {dp[i][0] = i;}for (let j = 1; j <= word2.length; j++) {dp[0][j] = j; }for (let i = 1; i <= word1.length; i++) {for (let j = 1; j <= word2.length; j++) {if (word1[i - 1] === word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;}}}return dp[word1.length][word2.length];
};

分析:时间复杂度为 O(n * m),空间复杂度为 O(n * m)。

收获

练习使用动态规划法求解编辑距离问题。

相关文章:

【LeetCode】72. 编辑距离(中等)——代码随想录算法训练营Day55

题目链接&#xff1a;72. 编辑距离 题目描述 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 示例 1&#xff1a; 输入&#xff1a;w…...

关于手机是否支持h264的问题的解决方案

目录 现象 原理 修改内容 现象 开始以为是手机不支持h264的编码 。机器人chatgpt一通乱扯。 后来检查了下手机&#xff0c;明显是有h264嘛。 终于搞定&#xff0c;不枉凌晨三点起来思考 原理 WebRTC 默认使用的视频编码器是VP8和VP9&#xff0c;WebRTC内置了这两种编码器…...

借助Aspose.html控件,在 Java 中将 URL 转换为 PDF

如果您正在寻找一种将实时 URL 中的网页另存为 PDF文档的方法&#xff0c;那么您来对地方了。在这篇博文中&#xff0c;我们将学习如何使用 Java 将 URL 转换为 PDF。从实时 URL转换HTML网页可以像任何其他文档一样保存所需的网页以供离线访问。将网页保存为 PDF 格式可以轻松突…...

数据结构——堆的应用 堆排序详解

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…...

Sftp服务器搭建(linux)

Sftp服务器搭建&#xff08;linux&#xff09; 一、基本工作原理 FTP的基本工作原理如下&#xff1a; 1&#xff09;建立连接&#xff1a;客户端与服务器之间通过TCP/IP建立连接。默认情况下&#xff0c;FTP使用端口号21作为控制连接的端口。​​​​​​​ 2&#xff09;身…...

Neo4j 新手教程 环境安装 基础增删改查 python链接 常用操作 纯新手向

Neo4j安装教程&#x1f680; 目前在学习知识图谱的相关内容&#xff0c;在图数据库中最有名的就是Neo4j,为了降低入门难度&#xff0c;不被网上很多华丽呼哨的Cypher命令吓退&#xff0c;故分享出该文档&#xff0c;为自己手动总结&#xff0c;包括安装环境&#xff0c;增删改查…...

PyTorch2.0 环境搭建详细步骤(Nvidia显卡)

Step 1 、查看显卡驱动版本 Step2、下载CUDA 11.7 或者11.8&#xff08;我自己用的这个&#xff09;也行,稍后我会贴出来版本匹配对应表 https://developer.nvidia.com/cuda-toolkit-archive Step3、下载CUDNN cuDNN 9.0.0 Downloads | NVIDIA Developer Step4、安装anconda&…...

Python逆向:pyc字节码转py文件

一、 工具准备 反编译工具&#xff1a;pycdc.exe 十六进制编辑器&#xff1a;010editor 二、字节码文件转换 在CTF中&#xff0c;有时候会得到一串十六进制文件&#xff0c;通过010editor使用查看后&#xff0c;怀疑可能是python的字节码文件。 三、逆向反编译 将010editor得到…...

提示词工程技术:类比、后退、动态少样本、自动生成CoT

类比提示 “类比提示”利用类比推理的概念&#xff0c;鼓励模型生成自己的例子和知识&#xff0c;从而实现更灵活和高效的解决问题。 后退提示 “后退提示”专注于抽象&#xff0c;引导模型推导出高级概念和原理&#xff0c;进而提高其推理能力。 使用一个基本的数学问题来…...

【深度学习笔记】6_5 RNN的pytorch实现

注&#xff1a;本文为《动手学深度学习》开源内容&#xff0c;部分标注了个人理解&#xff0c;仅为个人学习记录&#xff0c;无抄袭搬运意图 6.5 循环神经网络的简洁实现 本节将使用PyTorch来更简洁地实现基于循环神经网络的语言模型。首先&#xff0c;我们读取周杰伦专辑歌词…...

Linux at任务调度命令行编辑错误

错误&#xff1a; 在at任务调度命令行语句编辑错误时&#xff0c;按backspace进行删除无法进行。 解决方案&#xff1a; 请按Ctrlbackspace进行删除&#xff0c;即可解决。...

lua与C++粘合层框架

lua调用C++ 在lua中是以函数指针的形式调用函数, 并且所有的函数指针都必须满足如下此种类型: typedef int (*lua_CFunction) (lua_State *L);   也就是说, 偶们在C++中定义函数时必须以lua_State为参数, 以int为返回值才能被Lua所调用. 但是不要忘记了, 偶们的lua_State是支…...

POST 请求,Ajax 与 cookie

POST 请求则需要设置RequestHeader告诉后台传递内容的编码方式以及在 send 方法里传入对应的值 xhr.open("POST", url, true); xhr.setRequestHeader(("Content-Type": "application/x-www-form-urlencoded")); xhr.send("key1value1&…...

机器学习--循环神经网络(RNN)3

本篇文章结合具体的例子来介绍一下LSTM运算方式以及原理。请结合上篇文章的介绍食用。 一、具体例子 如上图所示&#xff0c;网络里面只有一个 LSTM 的单元&#xff0c;输入都是三维的向量&#xff0c;输出都是一维的输出。 这三维的向量跟输出还有记忆元的关系是这样的。 假设…...

Android Studio编译及调试知识

文章目录 Android Studio编译kotlin项目Android Studio编译Java和kotlin混合项目的过程gradle打印详细错误信息&#xff0c;类似这种工具的使用Android apk 从你的代码到APK打包的过程&#xff0c;APK安装到你的Android手机上的过程&#xff0c;最后安装好的形态&#xff0c;以…...

Fastjson 1.2.24 反序列化导致任意命令执行漏洞复现(CVE-2017-18349)

写在前面 CVE-2017-18349 指的是 fastjson 1.2.24 及之前版本存在的反序列化漏洞&#xff0c;fastjson 于 1.2.24 版本后增加了反序列化白名单&#xff1b; 而在 2019 年&#xff0c;fastjson 又被爆出在 fastjson< 1.2.47 的版本中&#xff0c;攻击者可以利用特殊构造的 …...

Spring Boot 注解教程

Spring Boot 注解教程 在 Spring 和 Spring Boot 的世界里&#xff0c;注解&#xff08;Annotations&#xff09;起着至关重要的作用。它们为开发者提供了声明式编程的能力&#xff0c;大大简化了 Spring 应用的开发过程。在这篇博客中&#xff0c;我们将探讨 Spring Boot 中的…...

Day32-计算机基础2

Day32-计算机基础2 1. 什么是网络拓扑(Network Topology)&#xff1f;2. 网络拓扑3种经典模型2.1 网络拓扑结构-总线型2.2 网络拓扑结构-环形2.3 星型&#xff1a;2.4 网络拓扑结构总结 3.OSI网络模型概念*****3.1 OSI的概念&#xff1a;open system interconnect 开放系统互连…...

Stable Diffusion WebUI 中英文双语插件(sd-webui-bilingual-localization)并解决了不生效的情况

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里。 大家好&#xff0c;我是水滴~~ 本文介绍一款中英文对照插件 sd-webui-bilingual-localization&#xff0c;该插件可以让你的 Stable Diffusion WebUI 界面同时显示中文和英文&#xff0c;让我…...

AndroidStudio连不上adb报错ADB Connection Error

之前笔者一直通过AndroidStudio来看日志&#xff0c;也一直用的一套自己的SDK&#xff0c;用了好几年了。 但是突然有一天&#xff0c;AndroidStudio启动后就弹出警告窗&#xff1a;ADB Connection Error&#xff0c;如下&#xff1a; 在Event Log面板还持续性的输出&#x…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

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

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

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...