当前位置: 首页 > 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;而即席查询是由用户自定义查…...

PROJECT MOGFACE技术解析:深入理解LSTM在序列建模中的替代与增强

PROJECT MOGFACE技术解析&#xff1a;深入理解LSTM在序列建模中的替代与增强 1. 引言 如果你在几年前接触过自然语言处理或者语音识别&#xff0c;那么“LSTM”这个词对你来说一定不陌生。它曾经是处理序列数据的黄金标准&#xff0c;从机器翻译到语音合成&#xff0c;几乎无…...

高效统计分析实战指南:JASP全面解析与应用秘籍

高效统计分析实战指南&#xff1a;JASP全面解析与应用秘籍 【免费下载链接】jasp-desktop JASP aims to be a complete statistical package for both Bayesian and Frequentist statistical methods, that is easy to use and familiar to users of SPSS 项目地址: https://…...

保姆级教程:用300条数据微调SenseVoice语音模型(附数据格式详解)

300条数据高效微调SenseVoice语音模型的实战指南 去年在为一个医疗咨询项目定制语音识别系统时&#xff0c;我发现通用模型对专业医学术语的识别准确率不足60%。当时团队仅有400条标注数据&#xff0c;却通过SenseVoice的微调功能在3小时内将准确率提升至89%。本文将分享这种小…...

Java八股文实战:从cv_resnet101模型服务理解RPC与序列化

Java八股文实战&#xff1a;从cv_resnet101模型服务理解RPC与序列化 你是不是也遇到过这种情况&#xff1f;面试时被问到“RPC和HTTP有什么区别&#xff1f;”、“序列化协议怎么选&#xff1f;”&#xff0c;脑子里全是书本上的概念&#xff0c;什么“远程过程调用”、“轻量…...

构建自主海上防御系统:Mirai Robotics融资420万美元

Mirai Robotics已筹集420万美元的Pre-Seed轮资金&#xff0c;旨在构建自主和智能的海上系统。本轮融资由Primo Ventures、Techshop和40Jemz Ventures领投&#xff0c;并有来自意大利和国际的天使投资人参与。 海洋是地球上最关键的基础设施之一。全球超过80%的贸易通过海路运输…...

ArduPilot开源飞控之飞行模式切换机制解析

1. ArduPilot飞行模式概述 第一次接触ArduPilot时&#xff0c;最让我震撼的就是它丰富的飞行模式。就像开车时有手动挡、自动挡、运动模式一样&#xff0c;无人机也需要根据不同的飞行场景选择合适的"驾驶模式"。举个例子&#xff0c;新手练习时用Stabilize模式就像开…...

用Matlab/Simulink手把手教你设计交错式升压DC-DC转换器(附PI参数整定代码)

从零构建交错式升压DC-DC转换器的MATLAB实战指南 交错式升压拓扑正在新能源领域掀起一场静默革命——当电动汽车的电池管理系统需要稳定升压时&#xff0c;当光伏逆变器要处理不稳定的直流输入时&#xff0c;这种能显著降低电流纹波的结构已成为工程师的秘密武器。但理论图纸与…...

双模型对比:OpenClaw接入Qwen3.5-4B-Claude与原版效果实测

双模型对比&#xff1a;OpenClaw接入Qwen3.5-4B-Claude与原版效果实测 1. 测试背景与实验设计 去年在开发一个自动化文档处理工具时&#xff0c;我发现OpenClaw的任务成功率高度依赖底层模型的逻辑推理能力。当时使用的标准Qwen模型在处理多步骤任务时经常出现"跳步&quo…...

CVPR 2025前瞻:计算机视觉三大技术革新与应用场景

1. 三维重建&#xff1a;从实验室走向真实世界 记得我第一次接触三维重建技术是在2015年&#xff0c;当时还在用传统的SFM&#xff08;Structure from Motion&#xff09;方法处理无人机航拍图像。十年后的今天&#xff0c;看着CVPR 2025上涌现的新技术&#xff0c;不得不感叹…...

OPC UA Web访问避坑指南:如何选择RESTful、WebSocket还是GraphQL?

OPC UA Web访问技术选型实战&#xff1a;RESTful、WebSocket与GraphQL深度对比 工业物联网领域的技术架构师们经常面临一个关键决策&#xff1a;如何为OPC UA服务器选择最合适的Web访问方式&#xff1f;这个问题看似简单&#xff0c;却直接影响着系统性能、开发效率和长期维护成…...