【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…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
