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

LeetCode hot 100—编辑距离

news 来源：原创 2025/9/16 3:21:36

题目

给你两个单词 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')

分析

这是一个经典的动态规划问题，也叫莱文斯坦距离（Levenshtein distance）。可以使用动态规划的方法来求解将 word1 转换成 word2 所使用的最少操作数。

动态规划

算法思路

定义状态
设 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最少操作数。这里 i 和 j 的范围分别是从 0 到 word1.length() 和 word2.length()。

初始化边界条件

当 i = 0 时，意味着 word1 为空字符串，那么将空字符串转换成 word2 的前 j 个字符需要 j 次插入操作，所以 dp[0][j] = j。
当 j = 0 时，意味着 word2 为空字符串，那么将 word1 的前 i 个字符转换成空字符串需要 i 次删除操作，所以 dp[i][0] = i。

状态转移方程

如果 word1[i - 1] == word2[j - 1]，说明当前字符相等，不需要进行额外操作，那么 dp[i][j] = dp[i - 1][j - 1]。
如果 word1[i - 1] != word2[j - 1]，则可以进行三种操作：
插入操作：要使 word1 的前 i 个字符变成 word2 的前 j 个字符，可以先让 word1 的前 i 个字符变成 word2 的前 j - 1 个字符，再插入一个字符，即 dp[i][j] = dp[i][j - 1] + 1。
删除操作：先让 word1 的前 i - 1 个字符变成 word2 的前 j 个字符，再删除 word1 的第 i 个字符，即 dp[i][j] = dp[i - 1][j] + 1。
替换操作：先让 word1 的前 i - 1 个字符变成 word2 的前 j - 1 个字符，再将 word1 的第 i 个字符替换成 word2 的第 j 个字符，即 dp[i][j] = dp[i - 1][j - 1] + 1。
综合这三种操作，取最小值作为 dp[i][j] 的值，即 dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)。

最终结果
最终结果为 dp[word1.length()][word2.length()]，即把 word1 的全部字符转换成 word2 的全部字符所需的最少操作数。

时间复杂度：O( $mn$ )， $m$ 是 word1 的长度， $n$ 为 word2 的长度

空间复杂度：O( $mn$ )

class Solution {
public:int minDistance(std::string word1, std::string word2) {int m = word1.length();int n = word2.length();// 创建 dp 数组std::vector<std::vector<int>> dp(m + 1, std::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;}// 填充 dp 数组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] = std::min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1;}}}return dp[m][n];}
};

LeetCode hot 100—编辑距离

题目给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作： 插入一个字符删除一个字符替换一个字符示例示例 1： 输入：word1 "horse", word2 &q…...

编程日记 2025/9/16 3:21:36

SAP系统年终结算出错

问题描述：2024年采购订单发票校验过账到2024年时提示错误如下： 问题原因：2024年全部未结束的采购申请和订单被结转到2025年。解决方法：用事务代码FMJ3冲销此采购订单结转。...

编程日记 2025/8/17 19:39:51

在 Dev-C++中编译运行GUI 程序介绍（二）示例：祝福程序

在 Dev-C中编译运行GUI 程序介绍（二）示例：祝福程序前期见： 在 Dev-C中编译运行GUI 程序介绍（一）基础 https://blog.csdn.net/cnds123/article/details/147019078 示例1、祝福程序本文中的这个祝福程序是…...

编程日记 2025/9/7 17:24:40

Uniapp使用onShow语法报before initialization

一、错误原因分析函数未完成初始化时被调用 • 当你在 onShow 生命周期中调用 getUserMessagePlan() 时，如果该函数的定义位于调用代码的下方（如示例中的顺序），JavaScript 引擎会因变量提升规则抛出此错误。 • 示例代码结构&a…...

编程日记 2025/9/11 3:15:35

大模型在儿童急性淋巴细胞白血病（ALL）-初治患者诊疗中应用的研究报告

目录一、绪论 1.1 研究背景与意义 1.2 国内外研究现状 1.3 研究目的与内容二、大模型技术与儿童 ALL 相关知识 2.1 大模型技术原理与特点 2.2 儿童 ALL 的病理生理与诊疗现状三、术前风险预测与手术方案制定 3.1 术前数据收集与预处理 3.2 大模型预测术前风险 3.…...

编程日记 2025/9/16 1:57:14

如何选择适合机床的丝杆支撑座型号？

在机床中选择丝杆支撑座型号时，需综合考虑机械性能、安装条件及应用需求，接下来我们一起来看看详细的选型指南！ 1、‌适配性‌：丝杆支撑座应与所使用的滚珠丝杆完全适配，确保两者在尺寸、规格、性能等方面相互匹配。 2…...

编程日记 2025/9/8 1:29:44

「The Road to Web3 Cloud」香港活动回顾｜波卡的 Web3 Cloud 愿景

在区块链基础设施的发展浪潮中，Polkadot 正在迈出决定性的一步：打造一个属于 Web3 的 “云服务平台”。如果说 Bitcoin 创造了一个计算器，以太坊创造了一个计算机，那么 Polkadot 正在做的则是构建链上的 “云服务器”。它的目标是…...

编程日记 2025/9/12 9:10:59

PostgreSQL-容器运行时索引修复

在 Docker 中运行的 PostgreSQL 数据库如果索引损坏，可以通过以下步骤进行修复。索引损坏可能会导致查询性能下降或数据不一致，因此需要及时处理。 1. 进入 PostgreSQL 容器首先，进入运行 PostgreSQL 的 Docker 容器： <BASH&…...

编程日记 2025/9/13 20:27:18

Vanna + qwq32b 实现 text2SQL

Vanna 是一个开源的 Text-2-SQL 框架，主要用于通过自然语言生成 SQL 查询，它基于 RAG（Retrieval-Augmented Generation，检索增强生成）技术。Vanna 的核心功能是通过训练一个模型（基于数据库的元数据和用户提…...

编程日记 2025/9/11 6:39:18

100V5A同步降压大功率芯片WD5105：高效电源管理的卓越之选

100V5A同步降压大功率芯片WD5105：高效电源管理的卓越之选在现代电子设备的复杂电源架构中，对高效、稳定且可靠的电源管理芯片需求日益增长。WD5105作为一款100V5A同步降压大功率芯片，凭借其出色的性能、全面的保护机制以及广泛的应用适应性…...

编程日记 2025/9/7 16:27:02

springboot中测试python脚本：ProcessBuilder

目录一.添加Jython依赖二.使用步骤 1. 创建 ProcessBuilder 实例 2. 设置工作目录（可选） 3. 合并错误流（可选） 4. 启动进程 5. 处理输入输出流 6. 等待进程完成 7.完整案例三.注意事项 ProcessBuilder是jdk提供的脚本…...

编程日记 2025/9/10 6:11:59

Google Chrome下载受限制的解决方案【方法指南】

在国内使用网络时，部分用户在尝试访问Google Chrome官网下载谷歌浏览器时，常常遇到网页无法打开或文件下载失败的情况。这种下载受限制的问题多由网络访问政策或DNS解析异常导致。为了正常获取Google Chrome的最新版安装程序，用户需要通过一些…...

编程日记 2025/9/13 8:55:51

mysql-锁的算法(记录锁、间隙锁、临键锁)

1.行锁的三种算法有3种行锁算法，分别是： Record Lock：单个行记录上的锁，没有主键，会使用隐式的主键进行锁定Gap Lock：间隙锁，锁定一个范围，但不包含记录本身Next-Key Lock&#x…...

编程日记 2025/9/11 20:07:40

SAP Business One系统标准功能之外的不允许负库存控制

SqlServer版本写法： --在存储过程SBO_SP_TransactionNotification里加上这段代码，记得定义一个全局变量用于接收提醒具体是哪个物料 IF transaction_type IN (A) BEGINIF EXISTS (SELECT 1 FROM OIVL T0INNER JOIN OITW T1 ON T0.ItemCode T1.ItemCode…...

编程日记 2025/9/4 0:58:58

AI与5G的融合：如何实现更快速、更智能的物联网应用？

引言 AI和5G的结合，正在加速物联网（IoT）应用的发展，让万物互联变得更加智能、高效。5G提供超高速率、低时延和海量连接的网络能力，而AI则赋予物联网设备更强的数据分析、预测和自动决策能力。当AI与5G融合，…...

编程日记 2025/9/4 17:03:55

Redis的哨兵

Redis的哨兵 Sentinel 一.哨兵概念1.相关名词解释图二.主节点恢复方式1.人工恢复主节点故障流程图2.哨兵自动恢复主节点流程三.使用docker搭建环境1.安装docker-compose2.安装docker3.停止之前的redis服务器4.使用docker获取到redis的镜像5.使用docker-compose进行容器编排创…...

编程日记 2025/9/15 6:40:53

初识Redis · 简单理解Redis

目录前言： 分布式系统开源节流认识Redis 负载均衡缓存微服务前言： 本文只是作为Redis的一篇杂谈，简单理解一下Redis为什么要存在，以及它能做到和它不能做到的事儿，简单提及一下它对应的优势有什么&#…...

编程日记 2025/9/11 19:07:18

Python设计模式-抽象工厂模式

1. 什么是抽象工厂模式抽象工厂模式（Abstract Factory Pattern）是一种创建型设计模式，它提供了一种方式来创建一系列相关或相互依赖的对象，而无需指定它们具体的类。这种模式是所有形式的工厂模式中最为抽象和最具一般性的一种。…...

编程日记 2025/9/10 1:27:23

【中检在线-注册安全分析报告】

前言由于网站注册入口容易被黑客攻击，存在如下安全问题： 1. 暴力破解密码，造成用户信息泄露 2. 短信盗刷的安全问题，影响业务及导致用户投诉 3. 带来经济损失，尤其是后付费客户，风险巨大，造…...

编程日记 2025/9/9 4:11:31

试题代码 sys.h #ifndef __SYS_H__ #define __SYS_H__#include <STC15F2K60S2.H> //sys.c extern unsigned char UI; //界面标志(0湿度界面、1参数界面、2时间界面) extern unsigned char time; //时间间隔(1s~10S) extern bit ssflag; //启动/停止标志…...

编程日记 2025/9/11 20:10:36

软件系统安全设计方案，信息化安全建设方案（Word原件）

1.1 总体设计 1.1.1 设计原则 1.2 物理层安全 1.2.1 机房建设安全 1.2.2 电气安全特性 1.2.3 设备安全 1.2.4 介质安全措施 1.3 网络层安全 1.3.1 网络结构安全 1.3.2 划分子网络 1.3.3 异常流量管理 1.3.4 网络安全审计 1.3.5 网络访问控制 1.3.6 完…...

编程日记 2025/9/12 20:30:36

UE5 尝试接入 C# 脚本方案

最近团结替代 Unity6 的事官宣了，只能唏嘘不已，顺带的也就研究了一下在 UE5 中接入 C# 的方案，也算是提前帮广大 Unity 开发者蹚一下转 UE 的路~ 当前我发现的，维护比较勤快的 UE C# 方案有2个，UnrealCSharp 和 Unrea…...

编程日记 2025/9/12 17:43:29

力扣hot100 81-90记录

81-90（动态规划） leetcodehot100 81： class Solution { public:int climbStairs(int n) {int p 0, q 0, count 1;for(int i 1; i < n; i){p q; q count;count p q;}return count;} };//81class Solution { public:vector<vect…...

编程日记 2025/9/10 8:41:50

深入解析以太坊虚拟机（EVM）架构与状态机特性

以太坊（Ethereum）作为第二代区块链平台，其不仅仅是一部分布式账本，而是一个支持智能合约与去中心化应用（DApps）的全球计算机。其核心架构中，以太坊虚拟机（Ethereum Virtual Machine&…...

编程日记 2025/9/14 1:31:25

MySQL---Ubuntu环境安装

1.首先我们要安装MySQL的安装包（APT 配置包） 这个是适合我的Ubuntu版本的MySQL安装包下载安装包（MySQL APT 配置包） wget https://dev.mysql.com/get/mysql-apt-config_0.8.17-1_all.deb2.安装 APT 配置包： sudo d…...

编程日记 2025/9/9 3:23:05

Vue 3 中 ref 与 reactive 的对比

Vue 3 中 ref 与 reactive 的对比 Vue 3 中 ref 与 reactive 的对比一、定义和基本使用refreactive 二、响应式原理refreactive 三、适用场景refreactive 四、注意事项refreactive Vue 3 中 ref 与 reactive 的对比在 Vue 3 中，ref 和 reactive 都是用于创建响应式…...

编程日记 2025/9/9 11:42:13

【数据结构 · 初阶】- 单链表

目录一.相关指针知识点二.链表 1.为什么学了顺序表还要学链表 2.优点三.实现 1.链表的打印 —— 理解链表结构 (2) 物理结构图 2.链表的尾插 —— 入门错误写法：tail ! NULL 总结： 正确代码物理图解： (2) 尾插整体代码 (思考…...

编程日记 2025/9/10 21:21:06

【前端】【React】useCallback的作用与使用场景总结

一、useCallback 的作用与使用场景总结 useCallback 是 React 提供的一个 Hook，用于缓存函数的引用，避免因为组件重新渲染而导致函数地址发生变化。它返回一个记忆（memoized）后的回调函数，只有当依赖项发生变化时才会…...

编程日记 2025/9/16 1:57:18

什么是 React Router？如何使用？

React Router 详解 1. 引言在现代 web 开发中，单页面应用（SPA）越来越流行，React 是构建 SPA 的热门库之一。React Router 是一个标准的路由库，专为 React 应用设计，允许开发者在应用中实现动态路由和 UR…...

编程日记 2025/9/14 1:31:29

jQuery 插件

在现代Web开发中，jQuery以其简洁的语法和强大的功能成为了前端开发者们喜爱的工具之一。为了进一步扩展jQuery的功能，社区贡献了大量的插件，使得开发者能够更加高效地实现各种复杂的交互效果和功能。本文将介绍什么是jQuery插件、如何编写自己…...

编程日记 2025/9/15 1:37:30

未来杭州：科技与茶香交织的生态诗篇

故事背景故事发生在中国浙江杭州，融合智能科技与传统茶文化，描绘未来城市中人与自然共生的诗意画卷。通过六个充满未来感的生态场景，展现科技如何重塑龙井茶园、古运河、西湖等经典地标，编织出一曲科技与人文共鸣的生态交响诗。 …...

编程日记 2025/9/11 7:04:22

微服务多模块构建feign项目过程与一些报错（2025详细版）

目录 1.eureka-server的注意事项 2.eureka-feign的注意事项 3.多模块构建feign项目过程 3.1创建父项目 3.2创建子项目eureka-server 3.3创建子项目eureka-provider 3.4创建子项目eureka-feign 3.5运行给个点赞谢谢 1.eureka-server的注意事项 eureka-server的yml文件…...

编程日记 2025/9/11 11:32:22

AWS云安全实践：基于CISA关键措施的检测与实施指南

1. 引言随着越来越多的组织将其基础设施迁移到云端，确保AWS环境的安全变得至关重要。美国网络安全与基础设施安全局(CISA)提出的关键措施为我们提供了一个可靠的框架。本文将探讨如何在AWS环境中实施这些措施，特别关注检测类别和可实施的关键措施。 2. AWS云安全中的CISA关…...

编程日记 2025/9/11 3:08:09

超越肉眼所见：一种利用视网膜光学相干断层扫描血管成像（OCTA）图像进行早期痴呆检测的关联模型|文献速递-深度学习医疗AI最新文献

Title 题目 Beyond the eye: A relational model for early dementia detection using retinal OCTA images 超越肉眼所见：一种利用视网膜光学相干断层扫描血管成像（OCTA）图像进行早期痴呆检测的关联模型 01 文献速递介绍阿尔茨海默病&…...

编程日记 2025/9/13 15:06:02

终端使用python出现segmentation fault (core dumped)的一种解法

有时候在终端输入python，希望交互式运行命令或者通过pdb调试，但是出现如下错误： [1] 7476 segmentation fault (core dumped) python 但是单独运行python xxx.py 或者 python -c "xxx" 又是可以的！ 经过与AI大模…...

编程日记 2025/9/12 0:38:30

分布式id生成算法（雪花算法 VS 步长id生成）

分布式ID生成方案详解：雪花算法 vs 步长ID 一、核心需求全局唯一性：集群中绝不重复有序性：有利于数据库索引性能高可用：每秒至少生成数万ID低延迟：生成耗时<1ms二、雪花算法（Snowflake） 1. 数据结构（64位） 0 | 0000000000 0000000000 0000000000 0000000000 0 |…...

编程日记 2025/9/14 6:41:43

h265为什么没有大范围应用

H.265（也称为 HEVC，High Efficiency Video Coding）是一种视频压缩标准，旨在提供比 H.264（AVC）更高的压缩效率。然而，尽管 H.265 在技术上具有许多优势，但其大范围应用受到了以下几个…...

编程日记 2025/9/12 0:17:49

Linux图形化界面

一、Linux图形化界面桌面对于Linux系统来说，只是一个应用程序，所以是可以移植的。 Linaro公司针对于半导体厂商推出的芯片，开发了ARM开发工具、Linux内核以及Linux发行版（包括Android及Ubuntu）。所以无需自己移植&am…...

编程日记 2025/9/12 0:14:34

LangChain-检索系统 (Retrieval)

检索系统 (Retrieval) 检索系统是LangChain的核心组件之一，它提供了从各种数据源获取相关信息的能力，是构建知识增强型应用的基础。本文档详细介绍LangChain检索系统的组件、工作原理和最佳实践。概述检索系统解决了大型语言模型知识有限和过时的问…...

编程日记 2025/9/10 14:09:47

【Linux】进程概念

目录一、进程概念 （一）什么是进程 （二）描述进程-PCB 二、fork创建进程 （一）bash概念 （二）如何创建子进程一、进程概念 （一）什么是进程结论&#x…...

编程日记 2025/9/8 16:37:28

【JavaScript】十七、事件委托（冒泡阶段的利用）

文章目录 1、事件委托2、tab栏切换案例：使用事件委托优化3、阻止元素默认行为 1、事件委托以送快递为例，某班有20名同学，每人有一个快递，快递员可以一个个送，需要送40次，很繁琐，换个方式&…...

编程日记 2025/8/22 17:59:01

Android InstalldNativeService::getAppSize源码分析

InstalldNativeService::getAppSize 是 Android 系统中用于计算应用程序存储空间的核心方法，其逻辑可分为以下几个关键模块（结合代码和上下文分析）： 一、基础校验与初始化 1. 权限校验通过 ENFORCE_UID(AID_SYSTEM) 确…...

编程日记 2025/9/14 8:16:18

微信小程序跳

/** * 画布文本换行绘制 * canvasContext 画布实例 * text 要写入的文本 * x 初始x轴位置 * y 初始y轴位置 * ySpacing 换行后，每行直接的间隔 * maxWidth 此文本写入画布的最大宽度，超过此宽度就换行 * color 文本颜色 * size 文本字体大小 * align 文本…...

编程日记 2025/9/9 4:30:32

openlayers入门01 -- 环境配置和初始化地图

openlayers入门 openlayers开发环境配置 1.下载VSCode 官网地址：https://code.visualstudio.com/ 点击Download for Windows 2.安装汉化插件和openlayers插件搜索chinese，下载Chinese (Simplified) (简体中文) Language Pack 更改语言并重启搜…...

编程日记 2025/9/12 21:34:17