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

时间管理大师:OpenClaw+nanobot自动规划每日日程

时间管理大师&#xff1a;OpenClawnanobot自动规划每日日程 1. 为什么需要AI日程规划助手 作为一个长期被多线程任务困扰的技术从业者&#xff0c;我一直在寻找能够真正理解我工作习惯的智能日程管理方案。市面上的日历应用大多只能机械地记录事件&#xff0c;而无法根据任务…...

RWKV7-1.5B-g1a作品分享:多轮追问下保持主题聚焦的能力验证

RWKV7-1.5B-g1a作品分享&#xff1a;多轮追问下保持主题聚焦的能力验证 1. 模型简介与测试背景 rwkv7-1.5B-g1a是基于RWKV-7架构的多语言文本生成模型&#xff0c;特别适合基础问答、文案续写、简短总结和轻量中文对话场景。本次测试将重点验证该模型在多轮对话中保持主题聚焦…...

从零到一:UniApp前端网页托管与自定义域名配置实战指南

1. 从零开始&#xff1a;UniApp前端网页托管全流程解析 第一次接触UniApp前端网页托管时&#xff0c;我也被各种专业术语搞得晕头转向。经过几个项目的实战&#xff0c;我发现这套流程其实就像租房子&#xff1a;你得先有个门牌号&#xff08;域名&#xff09;&#xff0c;再找…...

Windows 11 + VSCode + Conda:保姆级配置Depth-Anything-3环境,一次跑通不报错

Windows 11深度视觉开发环境搭建实战&#xff1a;从零配置Depth-Anything-3全流程指南 当我在深夜第三次面对满屏红色报错信息时&#xff0c;终于意识到AI视觉项目的环境配置从来不是简单的"复制粘贴命令"就能搞定。本文将带你完整走通Windows 11系统下使用VSCode和C…...

如何通过AI技术提升图表创作效率?Next AI Draw.io全攻略

如何通过AI技术提升图表创作效率&#xff1f;Next AI Draw.io全攻略 【免费下载链接】next-ai-draw-io 项目地址: https://gitcode.com/GitHub_Trending/ne/next-ai-draw-io 技术人员日常工作中常会遇到这样的困境&#xff1a;花几小时绘制的架构图需要频繁修改&#x…...

Hunyuan3D-2:AI驱动3D创作的4大技术突破

Hunyuan3D-2&#xff1a;AI驱动3D创作的4大技术突破 【免费下载链接】Hunyuan3D-2 High-Resolution 3D Assets Generation with Large Scale Hunyuan3D Diffusion Models. 项目地址: https://gitcode.com/GitHub_Trending/hu/Hunyuan3D-2 Hunyuan3D-2是一款基于大规模扩…...

Google Test进阶玩法:用测试夹具重构你的C++项目(CLion实战篇)

Google Test进阶实战&#xff1a;用测试夹具重构复杂C项目的工程化实践 当你的C项目从几百行扩展到几万行代码时&#xff0c;那些曾经简单的单元测试开始变得力不从心。测试用例之间出现隐蔽的状态依赖&#xff0c;setup代码重复率飙升&#xff0c;而每次运行测试套件的时间越来…...

Mist:macOS固件与安装程序下载管理终极指南

Mist&#xff1a;macOS固件与安装程序下载管理终极指南 【免费下载链接】Mist A Mac utility that automatically downloads macOS Firmwares / Installers. 项目地址: https://gitcode.com/GitHub_Trending/mis/Mist Mist是一款专为macOS设计的自动化工具&#xff0c;能…...

GPT-SoVITS应用场景解析:为视频配音、做有声书,简单又实用

GPT-SoVITS应用场景解析&#xff1a;为视频配音、做有声书&#xff0c;简单又实用 1. 引言&#xff1a;声音克隆技术带来的变革 想象一下&#xff0c;你正在制作一个短视频&#xff0c;需要为不同角色配音。传统方式要么自己录制&#xff08;效果可能不专业&#xff09;&…...

解锁DeerFlow:零基础搭建智能研究环境完全指南

解锁DeerFlow&#xff1a;零基础搭建智能研究环境完全指南 【免费下载链接】deer-flow DeerFlow is a community-driven framework for deep research, combining language models with tools like web search, crawling, and Python execution, while contributing back to th…...