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

leetcode72. 编辑距离

leetcode72. 编辑距离

题目

在这里插入图片描述

思路

dp[i][j] 代表 word1i 位置转换成 word2j 位置需要最少步数,所以,

word1[i] == word2[j]dp[i][j] = dp[i-1][j-1]
word1[i] != word2[j]dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

其中,dp[i-1][j-1] 表示替换操作,dp[i-1][j] 表示对word1插入,dp[i][j-1] 表示对word2插入。

注意,针对第一行,第一列要单独考虑,我们引入 ‘’ 下图所示,初始化如下所示:
在这里插入图片描述

代码

class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]for i in range(len(word1)+1):dp[i][0] = ifor j in range(len(word2)+1):dp[0][j] = jfor i in range(1, len(word1)+1):for j in range(1, len(word2)+1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])return dp[-1][-1]

相关文章:

leetcode72. 编辑距离

leetcode72. 编辑距离 题目 思路 dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数,所以, 当 word1[i] word2[j],dp[i][j] dp[i-1][j-1]; 当 word1[i] ! word2[j],dp[i][j] 1 min(dp[i-1][j-1]…...

R语言的数据类型与数据结构:向量、列表、矩阵、数据框及操作方法

R语言的数据类型与数据结构:向量、列表、矩阵、数据框及操作方法 介绍向量列表矩阵数据框 介绍 R语言拥有丰富的数据类型和数据结构,以满足各类数据处理和分析的需求。本文将分享R语言中的数据类型,包括向量、列表、矩阵、数据框等&#xff…...

第十六章 构建和配置 Nginx 以与 Web 网关配合使用 (Windows) - 将 NSD 与 Nginx 结合使用

文章目录 第十六章 构建和配置 Nginx 以与 Web 网关配合使用 (Windows) - 将 NSD 与 Nginx 结合使用将 NSD 与 Nginx 结合使用CSPNSD_pass hostname:portNum;CSP on; and CSP off;CSPFileTypes filetype1[ filetype2...];CSPNSD_response_headers_maxsize size;CSPNSD_connect_…...

数据中台:数字中国战略关键技术设施

文章目录 每日一句正能量前言为何要建设数据中台数据中台建设痛点数据中台学习资料聚焦前沿,方法论体系更新与时俱进,紧跟时代热点深入6大行业,提炼实践精华大咖推荐,数字化转型必备案头书购买链接赠书活动 每日一句正能量 人生之…...

mac上更改vscode快捷键

以移动当前行代码为例 mac上的vscode,默认移动当前行代码的快捷键是⌥↑即option↑按键 现在我想改成command↑ 步骤如下 1.打开vscode-code-首选项-键盘快捷键 2.打开快捷键列表 3.输入move line,找到要改动的这个快捷键 当前行-右键-更改键绑定&…...

Day18:信息打点-小程序应用解包反编译动态调试抓包静态分析源码架构

目录 小程序获取-各大平台&关键字搜索 小程序体验-凡科建站&模版测试上线 小程序抓包-Proxifier&BurpSuite联动 小程序逆向-解包反编译&动态调试&架构 思维导图 章节知识点 Web:语言/CMS/中间件/数据库/系统/WAF等 系统:操作系…...

真实案例分享:MOS管电源开关电路,遇到上电冲击电流超标

做硬件,堆经验。 分享一个案例:MOS管电源开关电路,遇到上电冲击电流超标,怎么解决的呢? 下面是正文部分。 —— 正文 —— 最近有一颗用了挺久的MOSFET发了停产通知,供应链部门找到我们研发部门&#xff0c…...

LCR 164. 破解闯关密码

解题思路&#xff1a; 贪心 class Solution {public String crackPassword(int[] password) {String[] strs new String[password.length];for(int i 0; i < password.length; i)strs[i] String.valueOf(password[i]);Arrays.sort(strs, (x, y) -> (x y).compareTo(…...

【鸿蒙 HarmonyOS 4.0】常用组件:List/Grid/Tabs

一、背景 列表页面&#xff1a;List组件和Grid组件&#xff1b; 页签切换&#xff1a;Tabs组件&#xff1b; 二、列表页面 在我们常用的手机应用中&#xff0c;经常会见到一些数据列表&#xff0c;如设置页面、通讯录、商品列表等。下图中两个页面都包含列表&#xff0c;“…...

打造经典游戏:HTML5与CSS3实现俄罗斯方块

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…...

什么是系统工程(字幕)48

0 00:00:00,760 --> 00:00:03,550 那这里我们要说一下 1 00:00:04,050 --> 00:00:06,163 你看&#xff0c;刚才我们这里 2 00:00:06,163 --> 00:00:06,740 3 00:00:07,440 --> 00:00:13,460 这个我们把它说成&#xff0c;打开这个&#xff0c;关闭这个 4 00:00:…...

Jenkins发送邮件、定时执行、持续部署

集成Allure报告只需要配置构建后操作即可。但如果是web自动化&#xff0c;或是用HTMLTestRunner生成报告&#xff0c;构建后操作要选择Publish HTML reports&#xff0c;而构建中还要添加Execute system Groovy script插件&#xff0c;内容&#xff1a; System.setProperty(&q…...

Mysql的Cardinality值

什么是Cardinality值&#xff1f; Cardinality值是Mysql做索引优化时一个非常关键的值&#xff0c;优化器会根据这个值来判断是否使用这个索引&#xff0c;它表示索引中唯一值的数目估计值&#xff0c;该值应该尽可能接近1&#xff0c;如果非常小&#xff0c;则用户需要考虑是否…...

数据结构 - 栈和队列

本篇博客将介绍栈和队列的定义以及实现。 1.栈的定义 栈是一种特殊的线性表&#xff0c;只允许在固定的一端进行插入和删除数据&#xff0c;插入数据的一端叫做栈顶&#xff0c;另一端叫做栈底。栈中的数据遵守后进先出的原则 LIFO (Last In First Out)。 插入数据的操作称为压…...

C++:模版进阶 | Priority_queue的模拟实现

创作不易&#xff0c;感谢三连支持 一、非类型模版参数 模板参数分类为类型形参与非类型形参。 类型形参即&#xff1a;出现在模板参数列表中&#xff0c;跟在class或者typename之类的参数类型名称。 非类型形参&#xff0c;就是用一个常量作为类(函数)模板的一个参数&…...

【刷题记录】详谈设计循环队列

下题目为个人的刷题记录&#xff0c;在本节博客中我将详细谈论设计循环队列的思路&#xff0c;并给出代码&#xff0c;有需要借鉴即可。 题目&#xff1a;LINK 循环队列是线性表吗&#xff1f;或者说循环队列是线性结构吗&#xff1f; 对于这个问题&#xff0c;我们来看一下线…...

人工智能|机器学习——k-近邻算法(KNN分类算法)

1.简介 k-最近邻算法&#xff0c;也称为 kNN 或 k-NN&#xff0c;是一种非参数、有监督的学习分类器&#xff0c;它使用邻近度对单个数据点的分组进行分类或预测。虽然它可以用于回归问题&#xff0c;但它通常用作分类算法&#xff0c;假设可以在彼此附近找到相似点。 对于分类…...

乐得瑞 1C to 2C快充线:引领充电数据线新潮流,高效快充解决接口难题

随着科技的不断进步&#xff0c;数据线的接口种类也日渐繁多&#xff0c;但在早些时候&#xff0c;三合一和二合一的数据线因其独特的设计而备受欢迎。这类数据线通常采用USB-A口作为输入端&#xff0c;并集成了Micro USB、Lightning以及USB-C三种接口&#xff0c;满足了当时市…...

O2OA(翱途)开发平台如何在流程表单中使用基于Vue的ElementUI组件?

本文主要介绍如何在O2OA中进行审批流程表单或者工作流表单设计&#xff0c;O2OA主要采用拖拽可视化开发的方式完成流程表单的设计和配置&#xff0c;不需要过多的代码编写&#xff0c;业务人员可以直接进行修改操作。 在流程表单设计界面&#xff0c;可以在左边的工具栏找到Ele…...

0 OpenHarmony开源鸿蒙NEXT星河版内核嵌入式编程

开源鸿蒙NEXT星河版内核嵌入式编程 作者将狼才鲸创建日期2024-03-08 CSDN文章阅读地址Gitee文章下载地址 一、前景提要 2024年1月18日&#xff0c;华为放出HarmonyOS NEXT 鸿蒙星河版开发者预览版本&#xff08;不是HarmonyOS NEXT版&#xff0c;是HarmonyOS NEXT星河版&…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...