72.编辑距离
编辑距离是指通过删除、插入和替换三种操作，将一个字符串转换为另一个字符串所需的最少操作次数。
首先定义状态：dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。接下来定义状态转移方程：
- 如果
word1[i] == word2[j]，则dp[i][j] = dp[i - 1][j - 1]，因为字符相同，无需操作，当前状态等于上一个状态。 - 如果字符不同，则可以通过以下三种操作：
- 删除：
dp[i - 1][j] + 1，表示删除word1的前 i - 1个字符与word2的字符匹配，只有第i个字符不相同，删除它，使word1与word2的前j个字符相同。 - 插入：
dp[i][j - 1] + 1，表示在word1的前 i 个字符与word2的前 j - 1个字符相同，此时在word1末尾插入一个字符，使其与word2的前j个字符相同。 - 替换：
dp[i - 1][j - 1] + 1，表示将word1的当前字符替换为word2的当前字符，由于替换后两个字符相同等价于word1[i] == word2[j]，则状态与上一个状态相同，只是多了一次操作数。
- 删除：
最终，dp[i][j] 取这三种操作中的最小值。
代码
class Solution {
public://状态：将word1前 i 个字符变成 word2 前 j 个字符所需要的最少操作数int minDistance(string word1, string word2) {word1 = " " + word1,word2 = " " + word2;int m = word1.size(),n = word2.size();vector<vector<int>> dp(m + 1,vector<int>(n + 1));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] == word2[j]) {dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = min(dp[i - 1][j - 1],min(dp[i - 1][j],dp[i][j - 1])) + 1;}}}return dp[m][n];}
};时间复杂度：O（mn）,m，n分别为 word1 和 word2 的长度
空间复杂度：O（mn），用于存储状态值
相关文章：
72.编辑距离
编辑距离是指通过删除、插入和替换三种操作，将一个字符串转换为另一个字符串所需的最少操作次数。 首先定义状态：dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。接下来定义状态转移方程： 如果 word1[i]…...
自适应稀疏核卷积网络：一种高效灵活的图像处理方案
自适应稀疏核卷积网络：一种高效灵活的图像处理方案 引言 在深度学习的大潮中，计算机视觉技术取得了长足的进步。其中，卷积神经网络（CNN）作为图像处理的核心工具，极大地推动了各类图像识别任务的效果提升。…...
c# UTC 时间赋值注意事项
文章目录 最佳实践:赋值时指定时区问题描述回答关键区别：DateTime.SpecifyKind 的作用1. 直接赋值 DateTime.UtcNow.Date2. 使用 DateTime.SpecifyKind 强制指定 最佳实践:赋值时指定时区 避免 C# 版本默认读取时采用 机器时区问题 如果需要UTC 时间…...
对端服务器重装系统之后远程SSH无法登录的问题
今天遇到一个SSH连接问题特此记录下。 我之前可以从本机使用SSH跳转到其他服务器，今天突然发现无法跳转了，有警告信息，此报错是由于远程的主机的公钥发生了变化导致的，可能是有异常，建议修改认证文件后再次登录。 突然…...
豌豆 760 收录泛滥现象深度解析与应对策略
xinruanj 一、收录泛滥现象的具体表现 当用户在豌豆760 中搜索某类应用时，往往会被数量庞大、功能相似的程序所包围。以图片编辑类应用为例，搜索结果中可能会出现数十款名称相近、图标相似的应用。这些应用不仅在界面设计上缺乏创新，甚至部…...
dockers笔记
docker 和 虚拟机的区别 虚拟机比较笨重，包括操作系统 虚拟化：将物理资源虚拟为逻辑资源 镜像 - 模板 容器 - 实例 docker hub - 分享 和 复用 容器化和dockerfile dockerfile实践 我们想打印一个js语句，如何构建镜像完成这个事情 新建了…...
Angular | 利用 `ChangeDetectorRef` 解决 Angular 动态显示输入框的聚焦问题
在 Angular 应用开发中，实现用户点击按钮后，原地切换显示一个输入框并自动获取焦点的功能，是一个常见的交互模式。例如，搜索图标点击后变为搜索框，用户可以直接输入。然而，由于 Angular 的变更检测和 DOM 更…...
Redis——数据结构
Redis的五种基本数据类型：String、Hash、List、Set、ZSet 结构类型结构存储值结构读写能力String字符串、整数或浮点数对整个字符串或字符串的一部分进行操作；对整数或者浮点数进行自增或自减操作List链表，每个节点上包含一个字符串对链表两…...
)
通讯录管理系统(IO_序列化和反序列化版)
参照之前文章，也是IO的变版 package day4;import java.io.Serializable;/* 有需求 -- 才去设计类 自定义表示通讯录单条信息的类*/ public class PhoneBookItem implements Serializable {private static final long serialVersionUID 1L;//属性private String na…...
基于RT-Thread的STM32F4开发第三讲——DAC
文章目录 前言一、DAC是什么？二、RT-Thread工程创建三、DAC函数编写1.DAC.c2.DAC.h3.main.c 四、结果测试五、工程分享 前言 本章利用RT-Thread最新的驱动5.1.0开发DAC模块，使用的开发板是正点原子的STM32F4探索者。很多配置和上文重复，本文…...
git cherry-pick和git stash命令详解
git cherry-pick命令 定义 用于将指定的提交(commit)从一个分支"挑选"并应用到当前分支它复制某个提交的更改（diff），生成一个新的提交，保留原提交的更改内容，但拥有新的提交ID（SHA值）…...
MapReduce基本介绍
核心思想 分而治之：将大规模的数据处理任务分解成多个可以并行处理的子任务，然后将这些子任务分配到不同的计算节点上进行处理，最后将各个子任务的处理结果合并起来，得到最终的结果。 工作流程 Map 阶段： 输入数据被…...
正则表达式常用验证（一）
正则表达式（Regular Expression）是一种强大的文本匹配工具，常用于验证字符串的格式。以下是常见的正则表达式验证场景及其对应的表达式： 1. 数字验证 验证纯数字： ^\d+$示例：123、456789 验证固定长度的数字（如 6 位）： ^\d{6}$示例：123456 验证数字范围（如 1 到 100…...
基于几何布朗运动的股价预测模型构建与分析
基于几何布朗运动的股价预测模型构建与分析 摘要 本文建立基于几何布朗运动的股价预测模型，结合极大似然估计与蒙特卡洛模拟，推导股价条件概率密度函数并构建动态预测区间。实证分析显示模型在标普500指数预测中取得89%的覆盖概率，波动率估…...
通过SSRF击穿内网！kali-ssrf靶场实战！
目录 1. 靶场拓扑图 2. 判断SSRF的存在 3. SSRF获取本地信息 3.1. SSRF常用协议 3.2. 使用file协议 4. 172.150.23.1/24探测端口 5. 172.150.23.22 - 代码注入 6. 172.150.23.23 SQL注入 7. 172.150.23.24 命令执行 7.1. 实验步骤 8. 172.150.23.27:6379 Redis未授权…...
Yarn-概述
一、YARN 是什么？ YARN（Yet Another Resource Negotiator） 是 Apache Hadoop 生态系统中的核心组件，是一个 分布式资源管理和作业调度系统，主要用于协调集群中的计算资源（CPU、内存、磁盘、网络等…...
如何在sheel中运行spark
// 读取文件，得到RDD val rdd1 sc.textFile("hdfs://hadoop100:8020/wcinput/words.txt") // 将单词进行切割，得到一个存储全部单词的RDD val rdd2 fileRDD.flatMap(line > line.split(" ")) // 将单词转换为元组对象࿰…...
销售具备的能力有哪些
销售人员是许多公司业务的开拓者，他们的存在让公司的利益更高。因此，在许多的公司中，销售人员的待遇都非常的高。也因此，有的人看重销售人员的薪资待遇想寻找销售型的工作。但是，相当销售人员还需要具有一定的工作能力…...
React面试常问问题详解
以下是30个React面试中常见的问题及简要解析，涵盖基础概念、核心原理、性能优化、Hooks、状态管理等方面，适用于初中高级开发者准备面试时参考： 一、React 基础与核心概念 React 是什么？ React 是由 Facebook 开发的用于构建用户界…...
POM 和关键字驱动区别
一、POM 和关键字驱动的区别以及各自的优势分别是什么？ 1、POM 适用于对单个系统封装的自动化框架中，对业务覆盖更精准； 优势：更加便利、维护性更高 2、关键字驱动可以用于对多个业务、多个系统进行封装的自动化框架中&…...
2025年PMP 学习十一 第8章 项目质量管理（8.3）
第8章 项目质量管理（8.3） 文章目录 第8章 项目质量管理（8.3）8.3 控制质量1. 定义与作用2.输入、输出，工具和技术3. 数据收集 - 核查表（工具与技术）4. 数据展示 - 帕雷托图（工具与技术…...
【笔记】C++操作mysql及相关配置
目录 使用软件版本信息： 1. C配置mysql相关依赖 1.1 下载 1.2 文件配置 1.3 C编译器配置 2、测试程序 使用软件版本信息： Visual Studio 2022Mysql 8.0C Connector库 8.3.0 可直接在https://download.csdn.net/download/Word_And_Me_/90826524下…...
【MapReduce入门】深度解析MapReduce：定义、核心特点、优缺点及适用场景
目录 1 什么是MapReduce？ 2 MapReduce的核心特点 2.1 分布式处理 2.2 容错机制 3 MapReduce的完整工作流程 4 MapReduce的优缺点分析 4.1 优势 4.2 局限性 5 MapReduce典型应用场景 5.1 适用场景 5.2 不适用场景 6 MapReduce与其他技术的对比 7 总结 1…...
EMQX v5.0通过连接器和规则同步数据
1 概述 EMQX数据集成功能，帮助用户将所有的业务数据无需额外编写代码即可快速完成处理与分发。 数据集成能力由连接器和规则两部分组成，用户可以使用数据桥接或 MQTT 主题来接入数据，使用规则处理数据后，再通过数据桥接将数据发…...
JCJC 错别字检测自定义词典 API 接口文档 2025-05-13
JCJC 错别字检测自定义词典 API 接口文档 2025-05-13 JCJC 错别字检测系统自定义词典接口全面开放。企业用户和个人付费用户都可以使用接口方式管理自定义词典。 自定义词典包含： 白名单和黑名单两种类型。 也可以登录个人中心，点击左侧边栏导航以 UI …...
Qt 样式表qss学习
语法 /* 语法结构 */ selector { attribute: value }selector（选择器） selector（选择器）：指定要应用样式的控件类型或特定控件。例如： QWidget：所有QWidget及其子类。QPushButton：…...
Linux文件编程——读写结构体、链表等其他类型的数据
在 Linux 文件编程中， open、read、write、close等函数，本质上的读写内容是一个无类型的指针，所以其也可以读写整型、数组、结构体、链表等不同类型的数据。 SYNOPSIS #include <unistd.h>ssize_t write(int fd, const void *buf, siz…...
离散制造企业WMS+MES+QMS+条码管理系统高保真原型全解析
在离散型制造企业的生产过程中，库存管理混乱、生产进度不透明、质检流程繁琐等问题常常成为制约企业发展的瓶颈。为了帮助企业实现全流程数字化管控，我们精心打造了一款基于离散型制造企业（涵盖单件生产、批量生产、混合生产模式）…...
Datawhale PyPOTS时间序列5月第1次笔记
课程原地址： https://github.com/WenjieDu/PyPOTS（Package地址） https://github.com/WenjieDu/BrewPOTS/tree/datawhale/202505_datawhale（Tutorial地址） 2.1 PyPOTS简介 PyPOTS 是一个专为处理部分观测时间序列&a…...
linux 抓包工具tcpdump使用小记（使用时注意权限和系统资源）
tcpdump 是一款强大的网络数据包捕获和分析工具，常用于网络故障排查、协议分析、安全审计等场景。以下是其核心功能、使用方法及常见场景的详细介绍： 1. 基本功能 数据包捕获：监听网络接口，实时捕获传输的数据包。过滤规则&#…...
HTTP和HTTPS模块
一、HTTP 模块 1. 创建 HTTP 服务器 基本服务器示例 const http require(http);const server http.createServer((req, res) > {res.statusCode 200;res.setHeader(Content-Type, text/plain);res.end(Hello World\n); });server.listen(3000, 127.0.0.1, () > {co…...
操作系统导论——第29章 基于锁的并发数据结构
通过锁可以使数据结构线程安全（thread safe）。当然，具体如何加锁决定了该数据结构的正确性和效率？挑战是： 关键问题：如何给数据结构加锁？ 对于特定数据结构，如何加锁才能让该结构功能…...
TensorFlow之微分求导
目录 前言示例手动微分实现两个未知数, 求偏导tf.GradientTape常量求导tf.GradientTape二阶导数tf.GradientTape实现梯度下降结合optimizer实现梯度下降 前言 在TensorFlow中，微分是个非常重要的概念。它们分别用于自动求导（计算梯度）和高效…...
电池自动点焊机：多领域电池制造的核心设备
电池自动点焊机作为电池制造领域的关键设备，通过电阻热焊接技术实现金属连接片与电池极片的精确焊接，广泛应用于数码电池、工具电池、储能电池、电动车电池及动力电池的生产环节。其核心技术基于微电脑控制与多脉冲焊接模式，能够针对不同电池…...
第五部分：第一节 - Node.js 简介与环境：让 JavaScript 走进厨房
我们之前学习的 JavaScript 主要运行在浏览器中，由浏览器内置的 JavaScript 引擎（如 Chrome 的 V8 引擎）来解释执行。Node.js 则是一个JavaScript 运行时环境，它也使用了 Chrome 的 V8 引擎，但它不是在浏览器里&#x…...
MQTT 协议详解：物联网通信的利器
在当今物联网（IoT）迅猛发展的背景下，设备之间的高效、可靠通信变得尤为重要。MQTT（Message Queuing Telemetry Transport）作为一种轻量级的消息传输协议，因其低带宽占用和高可靠性，成为物联网领…...
CST软件对OPERACST软件联合仿真汽车无线充电站对人体的影响
上海又收紧了新能源车的免费上牌政策。所以年前一些伙伴和我探讨过买新能源汽车的问题，小伙伴们基本纠结的点是买插电还是纯电？我个人是很抗拒新能源车的，也开过坐过。个人有几个观点： 溢价过高，不保值。实际并不环保…...
C++STL——map和set的使用
目录 1.容器 1.1 序列容器 1.2 容器适配器 1.3 关联容器 1.4 无序关联容器 1.5 键值对到底是个什么东西？ 2.set系列的使用 2.1 set类的介绍 2.2 set的构造以及迭代器 2.3 set的增，删，查 2.3.1 插入 2.3.2 删除 2.3.3 查找 2.3.4…...
Ensemble Alignment Subspace Adaptation Method for Cross-Scene Classification
用于跨场景分类的集成对齐子空间自适应方法 摘要：本文提出了一种用于跨场景分类的集成对齐子空间自适应（EASA）方法，它可以解决同谱异物和异谱同物的问题。该算法将集成学习的思想与域自适应（DA）算法相结合…...
AFFS2 的 `yaffs_ext_tags` 数据结构详解
YAFFS2 的 yaffs_ext_tags 数据结构详解 yaffs_ext_tags 是 YAFFS2 文件系统中用于 管理 NAND 闪存页的元数据 的核心结构体，存储在 NAND 的 OOB（Out-Of-Band）区域。它记录了数据块的归属、状态、校验信息等关键元数据，是 YAFFS2…...
CSS经典布局之圣杯布局和双飞翼布局
目标： 中间自适应，两边定宽，并且三栏布局在一行展示。 圣杯布局 实现方法： 通过float搭建布局margin使三列布局到一行上relative相对定位调整位置； 给外部容器添加padding，通过相对定位调整左右两列的…...
超声波传感器模块
欢迎来到 破晓的历程的 博客 ⛺️不负时光，不负己✈️ 文章目录 1.HC-SR04介绍2.HC-SR04原理介绍2.1原理概述3.2原理详解 4驱动代码编写4.1写前思考4.2硬件连线 5.总结hcsr04.hhcsr04.c 1.HC-SR04介绍 超声波传感器有很多种类的型号：HC-SR04、UC-025、…...
使用scp命令拷贝hadoop100中文件到其他虚拟机中
以下是使用 scp 命令将 hadoop100 主机中的文件拷贝到其他虚拟机的操作步骤（假设其他主机名为 hadoop101 、 hadoop102 ，系统为 Linux）： 1. 基本语法 bash scp [选项] 源文件路径 目标主机用户名目标主机IP:目标路径 - 选…...
Linux基础 -- 用户态Generic Netlink库高性能接收与回调框架
用户态Generic Netlink库高性能接收与回调框架 一、概述 在 Linux 系统中，Netlink 是用户态与内核态通信的强大机制。libnl 是一个专为简化 Netlink 编程而设计的库，提供了接收和处理 Netlink 消息的高级接口。libnl-genl 是其通用 Netlink (Generic N…...
java中的Optional
在 Java 8 中，Optional 是一个用于处理可能为 null 的值的容器类，旨在减少空指针异常（NullPointerException）并提升代码的可读性。以下是 Optional 的核心用法和最佳实践： 1. 创建 Optional 对象 1.1 常规创建方式 Op…...
原型和原型链
原型（Prototype） 和 原型链（Prototype Chain） 是 JavaScript 中非常重要的概念，它们是 JavaScript 实现继承和共享属性和方法的核心机制。理解原型和原型链可以帮助你更好地掌握 JavaScript 的面向对象编程（…...
解锁Python TDD：从理论到实战的高效编程之道（9/10）
引言 在 Python 开发的广袤天地中，确保代码质量与稳定性是每位开发者的核心追求。测试驱动开发（TDD，Test-Driven Development）作为一种强大的开发理念与实践方法，正逐渐成为 Python 开发者不可或缺的工具。TDD 强调在…...
：STM32F103开发环境搭建)
OpenMCU(七)：STM32F103开发环境搭建
概述 本文主要讲述了使用Keil软件搭建STM32F103嵌入式开发环境的步骤，主要面向想从事嵌入式行业的入门同学，如果下面的讲述过程中有不对的地方，欢迎大家给我留言。 本文主要讲述了Keil 5.43的安装教程，主要用于学习交流…...
六、Hive 分桶
作者：IvanCodes 日期：2025年5月13日 专栏：Hive教程 在 Hive 中，除了常见的分区（Partitioning），分桶（Bucketing）是另一种重要且有效的数据组织和性能优化手段。它允许我们…...
INFINI Console 纳管 Elasticsearch 9（一）：指标监控、数据管理、DSL 语句执行
Elasticsearch v9.0 版本最近已发布，而 INFINI Console 作为一款开源的非常轻量级的多集群、跨版本的搜索基础设施统一管控平台，是否支持最新的 Elasticsearch v9.0 集群管理呢？本文以 INFINI Console v1.29.2 为例，从指标监控、数…...