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

力扣_字符串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...i1] w o r d 2 [ 0... j − 1 ] word2[0...j-1] word2[0...j1] 的编辑距离
  • 边界条件 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[i1]==word[j1] 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[i1][j]+1,dp[i][j1]+1,dp[i][j])
    • w o r d 1 [ i − 1 ] ! = w o r d [ j − 1 ] word1[i-1] != word[j-1] word1[i1]!=word[j1] 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[i1][j]+1,dp[i][j1]+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&#xff0c; 请返回将 w o r d 1 word1 word1 转换成 w o r d 2 word2 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 方法—动…...

MySQL篇----第二十篇

系列文章目录 文章目录 系列文章目录前言一、NULL 是什么意思二、主键、外键和索引的区别?三、你可以用什么来确保表格里的字段只接受特定范围里的值?四、说说对 SQL 语句优化有哪些方法?(选择几条)前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍…...

Promise 基础

Promise 基础 理解 抽象表达&#xff1a; Promise 是一门新的技术&#xff08;ES6 规范&#xff09;Promise 是 Js 中进行异步编程的新的解决方案&#xff08;旧方案是使用回调函数&#xff09; 具体表达 从语法上来说&#xff0c;Promise 是一个构造函数从功能上来说&#x…...

RPA财务机器人之UiPath实战 - 自动化操作Excel进行财务数据汇总与分析之流程建立与数据读取、处理、汇总、分析

一、案例介绍&#xff1a; A公司共有13个开在不同银行的帐户&#xff0c;分别用于不同的业务分部或地区分部收付款。公司总部为了核算每月的收支情况&#xff0c;查看银行在哪个月交易量频繁&#xff0c;需要每月汇总各个银行的帐户借方和贷方金额&#xff0c;并将其净收支&am…...

华为机试真题实战应用【赛题代码篇】-输入整型数组和排序标识/根据排序标识flag给数组排序(附Java、C++和python代码)

目录 问题描述 输出描述: 示例: 代码实现 Java 代码2 代码3 python...

【算法随想录01】环形链表

题目&#xff1a;141. 环形链表 难度&#xff1a;EASY 代码 哈希表遍历求解&#xff0c;表中存储的是元素地址。 时间复杂度 O ( N ) O(N) O(N)&#xff0c;空间复杂度 O ( N ) O(N) O(N) /*** Definition for singly-linked list.* struct ListNode {* int val;* …...

macOS Sonoma 14.3.1(23D60)发布

系统介绍 黑果魏叔2 月 9 日消息&#xff0c;苹果今日向 Mac 电脑用户推送了 macOS 14.3.1 更新&#xff08;内部版本号&#xff1a;23D60&#xff09;&#xff0c;本次更新距离上次发布隔了 17 天。 魏叔 查询苹果官方更新日志&#xff0c;macOS Sonoma 14.3.1 修复内容和 …...

2024-02-11 叮当鸭-平台系统-第三次重构-目标确定

摘要: 对平台系统的第三个版本&#xff0c;做总体规划&#xff0c;明确要达到的目标&#xff0c;功能需求&#xff0c;性能需求。 根据这些所要达到的目标&#xff0c;确定选择何种的方案。方案的成本评估单独进行&#xff0c;本文重点分析要达到的各种目标。 功能需求: 能和…...

Android7.0-Fiddler证书问题

一、将Fiddler的证书导出到电脑&#xff0c;点击Tools -> Options -> HTTPS -> Actions -> Export Root Certificate to Desktop 二、下载Window版openssl&#xff0c; 点击这里打开页面&#xff0c;下拉到下面&#xff0c;选择最上面的64位EXE点击下载安装即可 安…...

Kotlin:单例模式(项目使用实例)

摘要 单例模式主要的五种如下&#xff1a; 饿汉式懒汉式线程安全的懒汉式双重校验锁式&#xff08;Double Check)静态内部类式 一、项目使用单例模式实例场景 app在运行时缓存部分数据&#xff0c;作为全局缓存数据&#xff0c;以便其他页面及时更新页面对应状态的数据&…...

vue百度地图的和element输入框/v-region的联动

vue百度地图的使用 第一步&#xff1a;安装插件第二步&#xff1a;main.js中引用第三步&#xff1a;页面中使用 第一步&#xff1a;安装插件 npm install vue-baidu-map --save第二步&#xff1a;main.js中引用 // 百度地图 import BaiduMap from vue-baidu-map Vue.use(Baid…...

搜索+哈希/平衡树,LeetCode 987. 二叉树的垂序遍历

目录 一、题目 1、题目描述 2、接口描述 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 给你二叉树的根结点 root &#xff0c;请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言&#xff0c;其左右子结…...

蓝桥杯每日一题之内存问题

蓝桥杯真题---内存问题 题目描述&#xff1a; 小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。 为了简化问题&#xff0c;变量的类型只有以下三种&#xff1a; int&#xff1a;整型变量&#xff0c;一个 int 型变量占用 4 Byte 的内存空间。 long&#xff…...

Django前后端分离之后端实践2

小实践&#xff1a;实现用户登录、注销及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】信号

祝大家新年快乐啦&#xff01;&#xff01;&#xff01;新的一年&#xff0c;第一篇文章我们来谈谈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系统中&#xff0c;设置全局HTTP代理可以方便我们统一管理和控制网络请求。这不仅可以帮助我们加速网络访问&#xff0c;还可以在某些情况下绕过网络限制或实现匿名上网。下面&#xff0c;我将为你详细介绍在Linux系统中设置全局HTTP代理的步骤与技巧。 步骤一&#xf…...

即席查询框架怎么选?

怎么理解即席查询 即席查询&#xff08;Ad Hoc&#xff09;是用户根据自己的需求&#xff0c;灵活的选择查询条件&#xff0c;系统能够根据用户的选择生成相应的统计报表。即席查询与普通应用查询最大的不同是普通的应用查询是定制开发的&#xff0c;而即席查询是由用户自定义查…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...