力扣_字符串4—编辑距离
题目
给你两个单词 w o r d 1 word1 word1 和 w o r d 2 word2 word2, 请返回将 w o r d 1 word1 word1 转换成 w o r d 2 word2 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
方法—动态规划
- 定义 d p dp dp 数组, d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 w o r d 1 [ 0... i − 1 ] word1[0...i-1] word1[0...i−1] 与 w o r d 2 [ 0... j − 1 ] word2[0...j-1] word2[0...j−1] 的编辑距离
- 边界条件 d p [ 0 ] [ j ] = j , d p [ i ] [ 0 ] = i dp[0][j] = j, dp[i][0] = i dp[0][j]=j,dp[i][0]=i
- 转移:
- 若 w o r d 1 [ i − 1 ] = = w o r d [ j − 1 ] word1[i-1] == word[j-1] word1[i−1]==word[j−1], d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 , d p [ i ] [ j ] ) dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i][j]) dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1,dp[i][j])
- 若 w o r d 1 [ i − 1 ] ! = w o r d [ j − 1 ] word1[i-1] != word[j-1] word1[i−1]!=word[j−1], d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 , d p [ i ] [ j ] + 1 ) dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i][j]+1) dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1,dp[i][j]+1)
代码
class Solution {
public:int minDistance(string word1, string word2) {int n1 = word1.size();int n2 = word2.size();if(n1*n2 == 0)return n1+n2;vector<vector<int>> dp(n1+1, vector<int>(n2+1));for(int i = 1; i < n1+1; i++){dp[i][0] = i;}for(int i = 1; i < n2+1; i++){dp[0][i] = i;}for(int i = 1; i < n1+1; i++){for(int j = 1; j < n2+1; j++){if(word1[i-1] == word2[j-1]){dp[i][j] = min(dp[i-1][j]+1, min(dp[i][j-1]+1, dp[i-1][j-1]));}else{dp[i][j] = min(dp[i-1][j]+1, min(dp[i][j-1]+1, dp[i-1][j-1]+1));}}}return dp[n1][n2];}
};
相关文章:
力扣_字符串4—编辑距离
题目 给你两个单词 w o r d 1 word1 word1 和 w o r d 2 word2 word2, 请返回将 w o r d 1 word1 word1 转换成 w o r d 2 word2 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符删除一个字符替换一个字符 方法—动…...
MySQL篇----第二十篇
系列文章目录 文章目录 系列文章目录前言一、NULL 是什么意思二、主键、外键和索引的区别?三、你可以用什么来确保表格里的字段只接受特定范围里的值?四、说说对 SQL 语句优化有哪些方法?(选择几条)前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍…...
Promise 基础
Promise 基础 理解 抽象表达: Promise 是一门新的技术(ES6 规范)Promise 是 Js 中进行异步编程的新的解决方案(旧方案是使用回调函数) 具体表达 从语法上来说,Promise 是一个构造函数从功能上来说&#x…...
RPA财务机器人之UiPath实战 - 自动化操作Excel进行财务数据汇总与分析之流程建立与数据读取、处理、汇总、分析
一、案例介绍: A公司共有13个开在不同银行的帐户,分别用于不同的业务分部或地区分部收付款。公司总部为了核算每月的收支情况,查看银行在哪个月交易量频繁,需要每月汇总各个银行的帐户借方和贷方金额,并将其净收支&am…...
华为机试真题实战应用【赛题代码篇】-输入整型数组和排序标识/根据排序标识flag给数组排序(附Java、C++和python代码)
目录 问题描述 输出描述: 示例: 代码实现 Java 代码2 代码3 python...
【算法随想录01】环形链表
题目:141. 环形链表 难度:EASY 代码 哈希表遍历求解,表中存储的是元素地址。 时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( N ) O(N) O(N) /*** Definition for singly-linked list.* struct ListNode {* int val;* …...
macOS Sonoma 14.3.1(23D60)发布
系统介绍 黑果魏叔2 月 9 日消息,苹果今日向 Mac 电脑用户推送了 macOS 14.3.1 更新(内部版本号:23D60),本次更新距离上次发布隔了 17 天。 魏叔 查询苹果官方更新日志,macOS Sonoma 14.3.1 修复内容和 …...
2024-02-11 叮当鸭-平台系统-第三次重构-目标确定
摘要: 对平台系统的第三个版本,做总体规划,明确要达到的目标,功能需求,性能需求。 根据这些所要达到的目标,确定选择何种的方案。方案的成本评估单独进行,本文重点分析要达到的各种目标。 功能需求: 能和…...
Android7.0-Fiddler证书问题
一、将Fiddler的证书导出到电脑,点击Tools -> Options -> HTTPS -> Actions -> Export Root Certificate to Desktop 二、下载Window版openssl, 点击这里打开页面,下拉到下面,选择最上面的64位EXE点击下载安装即可 安…...
Kotlin:单例模式(项目使用实例)
摘要 单例模式主要的五种如下: 饿汉式懒汉式线程安全的懒汉式双重校验锁式(Double Check)静态内部类式 一、项目使用单例模式实例场景 app在运行时缓存部分数据,作为全局缓存数据,以便其他页面及时更新页面对应状态的数据&…...
vue百度地图的和element输入框/v-region的联动
vue百度地图的使用 第一步:安装插件第二步:main.js中引用第三步:页面中使用 第一步:安装插件 npm install vue-baidu-map --save第二步:main.js中引用 // 百度地图 import BaiduMap from vue-baidu-map Vue.use(Baid…...
搜索+哈希/平衡树,LeetCode 987. 二叉树的垂序遍历
目录 一、题目 1、题目描述 2、接口描述 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 给你二叉树的根结点 root ,请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言,其左右子结…...
蓝桥杯每日一题之内存问题
蓝桥杯真题---内存问题 题目描述: 小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。 为了简化问题,变量的类型只有以下三种: int:整型变量,一个 int 型变量占用 4 Byte 的内存空间。 longÿ…...
Django前后端分离之后端实践2
小实践:实现用户登录、注销及ORM管理功能、事务开启小实践 models.py class Books(models.Model):id models.CharField(primary_keyTrue,max_length20,verbose_name"图书ID")name models.CharField(max_length20,verbose_name图书名称)status models…...
windowsserver 2016 PostgreSQL9.6.3-2升级解决其安全漏洞问题
PostgreSQL 身份验证绕过漏洞(CVE-2017-7546) PostgreSQL 输入验证错误漏洞(CVE-2019-10211) PostgreSQL adminpack扩展安全漏洞(CVE-2018-1115) PostgreSQL 输入验证错误漏洞(CVE-2021-32027) PostgreSQL SQL注入漏洞(CVE-2019-10208) PostgreSQL 安全漏洞(CVE-2018-1058) …...
Java实现免税店商城管理系统 JAVA+Vue+SpringBoot+MySQL
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、系统设计2.1 功能模块设计2.2 研究方法 三、系统展示四、核心代码4.1 查询免税种类4.2 查询物品档案4.3 新增顾客4.4 新增消费记录4.5 审核免税 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的免税店商城管理系…...
【Linux】信号
祝大家新年快乐啦!!!新的一年,第一篇文章我们来谈谈Linux中的信号 目录 一、引入 二、系统内置的信号 三、前台进程和后台进程 四、signal函数 五、信号的产生 5.1 通过终端按键产生信号 5.2 调用系统函数向进程发信号 5…...
[NISACTF 2022]easyssrf
它提示我们输入 那我们输入file:///flag file:// 访问本地文件系统 它提醒我们输file:///fl4g 它提醒我们输ha1x1ux1u.php 看到代码stristr($file, “file”)当我们输入file它会提示我们输了 啥意思可以前面加个/ 也可以通过read读取 思路都是前面加/不等于flag绕过 filephp://…...
在Linux系统中设置全局HTTP代理的步骤与技巧
在Linux系统中,设置全局HTTP代理可以方便我们统一管理和控制网络请求。这不仅可以帮助我们加速网络访问,还可以在某些情况下绕过网络限制或实现匿名上网。下面,我将为你详细介绍在Linux系统中设置全局HTTP代理的步骤与技巧。 步骤一…...
即席查询框架怎么选?
怎么理解即席查询 即席查询(Ad Hoc)是用户根据自己的需求,灵活的选择查询条件,系统能够根据用户的选择生成相应的统计报表。即席查询与普通应用查询最大的不同是普通的应用查询是定制开发的,而即席查询是由用户自定义查…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
