【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 <= 500word1和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
题目链接:72. 编辑距离 题目描述 给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符删除一个字符替换一个字符 示例 1: 输入:w…...
关于手机是否支持h264的问题的解决方案
目录 现象 原理 修改内容 现象 开始以为是手机不支持h264的编码 。机器人chatgpt一通乱扯。 后来检查了下手机,明显是有h264嘛。 终于搞定,不枉凌晨三点起来思考 原理 WebRTC 默认使用的视频编码器是VP8和VP9,WebRTC内置了这两种编码器…...
借助Aspose.html控件,在 Java 中将 URL 转换为 PDF
如果您正在寻找一种将实时 URL 中的网页另存为 PDF文档的方法,那么您来对地方了。在这篇博文中,我们将学习如何使用 Java 将 URL 转换为 PDF。从实时 URL转换HTML网页可以像任何其他文档一样保存所需的网页以供离线访问。将网页保存为 PDF 格式可以轻松突…...
数据结构——堆的应用 堆排序详解
💞💞 前言 hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥个人主页&#x…...
Sftp服务器搭建(linux)
Sftp服务器搭建(linux) 一、基本工作原理 FTP的基本工作原理如下: 1)建立连接:客户端与服务器之间通过TCP/IP建立连接。默认情况下,FTP使用端口号21作为控制连接的端口。 2)身…...
Neo4j 新手教程 环境安装 基础增删改查 python链接 常用操作 纯新手向
Neo4j安装教程🚀 目前在学习知识图谱的相关内容,在图数据库中最有名的就是Neo4j,为了降低入门难度,不被网上很多华丽呼哨的Cypher命令吓退,故分享出该文档,为自己手动总结,包括安装环境,增删改查…...
PyTorch2.0 环境搭建详细步骤(Nvidia显卡)
Step 1 、查看显卡驱动版本 Step2、下载CUDA 11.7 或者11.8(我自己用的这个)也行,稍后我会贴出来版本匹配对应表 https://developer.nvidia.com/cuda-toolkit-archive Step3、下载CUDNN cuDNN 9.0.0 Downloads | NVIDIA Developer Step4、安装anconda&…...
Python逆向:pyc字节码转py文件
一、 工具准备 反编译工具:pycdc.exe 十六进制编辑器:010editor 二、字节码文件转换 在CTF中,有时候会得到一串十六进制文件,通过010editor使用查看后,怀疑可能是python的字节码文件。 三、逆向反编译 将010editor得到…...
提示词工程技术:类比、后退、动态少样本、自动生成CoT
类比提示 “类比提示”利用类比推理的概念,鼓励模型生成自己的例子和知识,从而实现更灵活和高效的解决问题。 后退提示 “后退提示”专注于抽象,引导模型推导出高级概念和原理,进而提高其推理能力。 使用一个基本的数学问题来…...
【深度学习笔记】6_5 RNN的pytorch实现
注:本文为《动手学深度学习》开源内容,部分标注了个人理解,仅为个人学习记录,无抄袭搬运意图 6.5 循环神经网络的简洁实现 本节将使用PyTorch来更简洁地实现基于循环神经网络的语言模型。首先,我们读取周杰伦专辑歌词…...
Linux at任务调度命令行编辑错误
错误: 在at任务调度命令行语句编辑错误时,按backspace进行删除无法进行。 解决方案: 请按Ctrlbackspace进行删除,即可解决。...
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运算方式以及原理。请结合上篇文章的介绍食用。 一、具体例子 如上图所示,网络里面只有一个 LSTM 的单元,输入都是三维的向量,输出都是一维的输出。 这三维的向量跟输出还有记忆元的关系是这样的。 假设…...
Android Studio编译及调试知识
文章目录 Android Studio编译kotlin项目Android Studio编译Java和kotlin混合项目的过程gradle打印详细错误信息,类似这种工具的使用Android apk 从你的代码到APK打包的过程,APK安装到你的Android手机上的过程,最后安装好的形态,以…...
Fastjson 1.2.24 反序列化导致任意命令执行漏洞复现(CVE-2017-18349)
写在前面 CVE-2017-18349 指的是 fastjson 1.2.24 及之前版本存在的反序列化漏洞,fastjson 于 1.2.24 版本后增加了反序列化白名单; 而在 2019 年,fastjson 又被爆出在 fastjson< 1.2.47 的版本中,攻击者可以利用特殊构造的 …...
Spring Boot 注解教程
Spring Boot 注解教程 在 Spring 和 Spring Boot 的世界里,注解(Annotations)起着至关重要的作用。它们为开发者提供了声明式编程的能力,大大简化了 Spring 应用的开发过程。在这篇博客中,我们将探讨 Spring Boot 中的…...
Day32-计算机基础2
Day32-计算机基础2 1. 什么是网络拓扑(Network Topology)?2. 网络拓扑3种经典模型2.1 网络拓扑结构-总线型2.2 网络拓扑结构-环形2.3 星型:2.4 网络拓扑结构总结 3.OSI网络模型概念*****3.1 OSI的概念:open system interconnect 开放系统互连…...
Stable Diffusion WebUI 中英文双语插件(sd-webui-bilingual-localization)并解决了不生效的情况
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 大家好,我是水滴~~ 本文介绍一款中英文对照插件 sd-webui-bilingual-localization,该插件可以让你的 Stable Diffusion WebUI 界面同时显示中文和英文,让我…...
AndroidStudio连不上adb报错ADB Connection Error
之前笔者一直通过AndroidStudio来看日志,也一直用的一套自己的SDK,用了好几年了。 但是突然有一天,AndroidStudio启动后就弹出警告窗:ADB Connection Error,如下: 在Event Log面板还持续性的输出&#x…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
