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

leetcode hot100 之 编辑距离

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

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

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

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

原题链接:https://leetcode.cn/problems/edit-distance/

思路

以 dp[i][j] 表示 word1[0: i]、word2[0: j] 的编辑距离。

转移方程:
当 word1[i] == word2[j] 时,此时无需操作,dp[i][j] = dp[i-1][j-1]
当 word1[i] != word2[j] 时,dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
这里 dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 三项分别代表 替换、删除、增加。

边界条件:
当 i = 0 或 j = 0 时,显然 dp[i][0] 或 dp[0][j] 等于另一个子字符串的长度。即 dp[i][0] = i 、dp[0][j] = j

代码

class Solution {
public:int minDistance(string word1, string word2) {// if word1[i] == word2[j], dp[i][j] = dp[i-1][j-1]// else: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1int m = word1.size();int n = word2.size();vector<vector<int>> dp(m+1, vector<int> (n+1, 0));for (int i = 0; i <= m; i++) {dp[i][0] = i;}for (int j = 0; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1[i-1] == word2[j-1]) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;}}}return dp[m][n];}
};

相关文章:

leetcode hot100 之 编辑距离

给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 输入&#xff1a;word1 “horse”, word2 “ros” 输出&#xff1a;3 解释&#xff1a…...

杨校老师项目之基于SpringBoot的理发店的预约管理系统

原系统是SSMJSP页面构成&#xff0c;先被修改为SpringBoot JSP页面 自助下载渠道: https://download.csdn.net/download/kese7952/89417001&#xff0c;或 点我下载 理发师信息&#xff1a; 理发师详细信息 公告信息 员工登录&#xff1a; 管理员登录...

SpringAI学习及搭建AI原生应用

文章目录 一、SpringAI是什么二、准备工作1.GPT-API-free2.AiCore3.eylink 三、对话案例实现1.创建项目2.实现简单的对话 四、聊天客户端ChatClient1.角色预设2.流式响应3.call和stream的区别 五、聊天模型提示词提示词模板 六、图像模型(文生图)七、语音模型1.文字转语音(文生…...

CobaltStrike权限传递MSF

一、测试环境 操作系统&#xff1a; 1.VMware17 2.kali 6.1.0-kali5-amd64 3.Win10x64 软件&#xff1a; 1.cs4.0 2.metasploit v6.3.4-dev 二、测试思路 1.cs是一款渗透测试工具&#xff0c;但没有漏洞利用的模块&#xff0c;我们可以在拿到目标主机的权限后&#xff0c;将…...

白嫖 kimi 接口 api

说明:kimi当然是免费使用的人工智能AI,但是要调用api是收费的. 项目&#xff1a; https://github.com/LLM-Red-Team/kimi-free-api 原文地址: https://blog.taoshuge.eu.org/p/272/ railway部署 步骤: 打开Github,新建仓库新建名为Dockerfile文件&#xff08;没有后缀&…...

借助ChatGPT完成课题申报书中框架思路写作指南

大家好&#xff0c;感谢关注。我是七哥&#xff0c;一个在高校里不务正业&#xff0c;折腾学术科研AI实操的学术人。可以和我&#xff08;yida985&#xff09;交流学术写作或ChatGPT等AI领域相关问题&#xff0c;多多交流&#xff0c;相互成就&#xff0c;共同进步 在课题申报…...

SuntoryProgrammingContest2024(AtCoder Beginner Contest 357)

https://www.cnblogs.com/yxcblogs/p/18239433 题解写到博客园了&#xff0c;懒得复制了&#xff0c;直接放个链接吧~...

重温共射放大电路

1、放大概念 小功率信号变成一个大功率信号&#xff0c;需要一个核心器件做这件事&#xff0c;核心器件的能量由电源提供&#xff0c;通过核心器件用小功率的信号去控制大电源&#xff0c;来实现能量的转换和控制&#xff0c;前提是不能失真&#xff0c;可以用一系列正弦波进行…...

[DDR5 Jedec] 读操作 Read Command 精讲

依公知及经验整理&#xff0c;原创保护&#xff0c;禁止转载。 专栏 《深入理解DDR》 Read 读取命令也可以视为列读取命令。当与正确的bank地址和列地址结合使用时&#xff0c;通过激活命令&#xff08;行访问&#xff09;移动到检测放大器中的数据&#xff0c; 现在被推送到数…...

opencv 通过滑动条调整阈值处理、边缘检测、轮廓检测、模糊、色调调整和对比度增强参数 并实时预览效果

使用PySimpleGUI库创建了一个图形用户界面(GUI),用于实时处理来自OpenCV摄像头的图像。它允许用户应用不同的图像处理效果,如阈值处理、边缘检测、轮廓检测、模糊、色调调整和对比度增强。用户可以通过滑动条调整相关参数。 完整代码在文章最后,可以运行已经测试; 代码的…...

防火墙安全管理

大多数企业通过互联网传输关键数据&#xff0c;因此部署适当的网络安全措施是必要的&#xff0c;拥有足够的网络安全措施可以为网络基础设施提供大量的保护&#xff0c;防止黑客、恶意用户、病毒攻击和数据盗窃。 网络安全结合了多层保护来限制恶意用户&#xff0c;并仅允许授…...

MyQueue(队列)

目录 一、队列的定义 二、队列方法的实现 1、定义队列 2、后端插入 3、前端操作 4、判断队列是否为空 5、队列大小 三、队列方法的使用 一、队列的定义 队列是一种特殊的线性表&#xff0c;特殊之处在于它只允许在表的前端&#xff08;front&#xff09;进行删除操作&am…...

【Pytorch】一文向您详细介绍 torch.nn.DataParallel() 的作用和用法

【Pytorch】一文向您详细介绍 torch.nn.DataParallel() 的作用和用法 下滑查看解决方法 &#x1f308; 欢迎莅临我的个人主页 &#x1f448;这里是我静心耕耘深度学习领域、真诚分享知识与智慧的小天地&#xff01;&#x1f387; &#x1f393; 博主简介&#xff1a;985高…...

Windows本地使用SSH连接VM虚拟机

WIN10 VM17.5 Ubuntu:20.04 1.网路设置 1)选择编辑->更改设置 配置完成 2.修改了服务器文件&#xff0c;修改sshd配置&#xff0c;在此文件下/etc/ssh/sshd_config&#xff0c;以下为比较重要的配置 PasswordAuthentication yes PermitRootLogin yes PubkeyAuthenticat…...

RPC(远程过程调用):技术原理、应用场景与发展趋势

摘要&#xff1a; RPC&#xff08;Remote Procedure Call&#xff09;是一种通信协议&#xff0c;用于实现跨网络的进程间通信。它提供了一种简单高效的方式&#xff0c;使得分布式系统中的不同组件能够像调用本地函数一样调用远程函数。本篇博客将介绍RPC的基本概念&#xff0…...

iSCSI和FC存储

iSCSI存储和FC存储的特点和区别 FC存储和iSCSI存储是两种主要的网络存储解决方案&#xff0c;它们各自在性能、成本和适用场景上有着不同的特点。 FC存储是一种基于光纤通道技术的高性能、低延迟的存储解决方案。它使用专用的光纤通道网络连接存储设备和服务器&#xff0c;确…...

MPT(merkle Patricia trie )及理解solidity里的storage

what&#xff1f; MPT树是一种数据结构&#xff0c;用于在以太坊区块链中高效地存储和检索账户状态、交易历史和其他重要数据。MPT树的设计旨在结合Merkle树和Patricia树的优点&#xff0c;以提供高效的数据存储和验证 MPT树由四种类型的节点组成&#xff1a; **扩展节点&…...

【代码随想录算法训练营第三十五天】 | 1005.K次取反后最大化的数组和 134.加油站 135.分发糖果

贪心章节的题目&#xff0c;做不出来看题解的时候&#xff0c;千万别有 “为什么这都没想到” 的感觉&#xff0c;想不出来是正常的&#xff0c;转变心态 “妙啊&#xff0c;又学到了新的思路” &#xff0c;这样能避免消极的心态对做题效率的影响。 134. 加油站 按卡哥的思路…...

桌面应用开发框架比较:Electron、Flutter、Tauri、React Native 与 Qt

在当今快速发展的技术环境中&#xff0c;对跨平台桌面应用程序的需求正在不断激增。 开发人员面临着选择正确框架之挑战&#xff0c;以便可以高效构建可在 Windows、macOS 和 Linux 上无缝运行的应用程序。 在本文中&#xff0c;我们将比较五种流行的桌面应用程序开发框架&…...

学习笔记丨嵌入式BI分析的12个关键功能

编者注&#xff1a;以下内容节选编译自嵌入式分析厂商Qrvey发表的《What is Embedded Analytics?》&#xff08;什么是嵌入式分析&#xff09;一文&#xff0c;作者为Qrvey产品市场主管Brian Dreyer。 什么是嵌入式分析&#xff1f; 嵌入式分析是指能够将数据分析的特性和功…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...