数据结构学习 Leetcode72 编辑距离

 关键词:动态规划 最长公共子序列

题目:

思路:

这题我虽然做出来了但是还是有点迷糊。首先,这道题一定是和最长公共子序列相似的。

所以往最长公共子序列方向思考,考虑的它的状态和转移方程以及边界。

状态和转移方程:

这里的替换 删除 插入需要好好琢磨一下。可以结合实际例子理解。

边界:

(第一次提交的时候没有注意,刚开始把边界都设成了intmax)

复杂度计算:

时间复杂度O(nm)

空间复杂度O(nm)

代码:

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
        if (word1.empty() || word2.empty()) //两个string里面至少有一个是空的
            return word1.length() + word2.length();
        //两个string都不空
        int n = word1.length() + 1;
        int m = word2.length() + 1;
        std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
        //边界
        for (int i = 0; i < dp[0].size(); ++i)
            dp[0][i] = i;
        for (int i = 0; i < dp.size(); ++i)
            dp[i][0] = i;
        //遍历每一个
        for (int i = 0; i < word2.length(); ++i)
        {
            for (int j = 0; j < word1.length(); ++j)
            {
                if (word1[j] == word2[i])
                    dp[i + 1][j + 1] = dp[i][j];
                else
                    dp[i + 1][j + 1] = std::min(std::min(dp[i][j], dp[i][j + 1]), dp[i + 1][j]) + 1;
            }
        }
        return dp[word2.length()][word1.length()];
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/279532.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Ajax学习

文章目录 AjaxAjax 是什么Ajax 经典应用场景Ajax 原理示意图ajax的异步请求的方法ajax的逻辑:应用实例-验证用户名是否存在思路框架图:需求分析: 到数据库去验证用户名是否可用思路框架图大功告成:使用JQuery-Ajax实现上面相同的需求:Ajax Ajax 是什么 AJAX 即"Async…

【HTML5】第1章 HTML5入门

学习目标 了解网页基本概念&#xff0c;能够说出网页的构成以及网页相关名词的含义 熟悉Web标准&#xff0c;能够归纳Web标准的构成。 了解浏览器&#xff0c;能够说出各主流浏览器的特点。 了解HTML5技术&#xff0c;能够知道HTML5发展历程、优势以及浏览器对HTML5的支持情…

【嵌入式开发学习必备专栏】

文章目录 嵌入式开发学习必备专栏1.1 ARM Coresight SoC-400/SoC-600 专栏导读目录1.1.1 Performance Profiling1.1.2 ARM Coresight Debug 工具系列1.1.2.1 ARM DS5 系列1.1.2.2 劳特巴赫 Trace32 系列1.1.2.3 JTAG OpenOCD 系列 1.2 ARM Cache 专栏1.3 ARM AMBA Bus 专栏1.3.…

java使用JSON工具解析字符串、数组详解

一&#xff1a;问题 1.最近自己在前后端数据交互时需要进行JSON格式字符串、数组数据进行转换&#xff0c;进行问题整理 2.遇到需要JSON字符串转换的朋友可以阅读 二&#xff1a;解析步骤 1.第一点首先确定需求&#xff0c;明确需要转的字符串是一个对象还是一个数组&#…

C练习——判断三角形并求面积

题目&#xff1a;从健盘任意输入三角形的三边长为a,b,c,编程判断a,b,c的值能否构成一个三角形&#xff0c;若能构成三角形&#xff0c;则计算并输出三角形的面积&#xff0c;否则提示不能构成三角形。 已知构成三角形的条件是&#xff1a;任意两边之和大于第三边。 解析&#…

jQuery-Validate验证插件的使用步骤【详解】

jQuery-Validate验证插件的使用步骤详解 1. 写在前面2. 效果展示3. Validate环境的搭建4. Validate基本方法的使用5. 实现错误消息的本地化6. 实现远程验证7. 自定义验证方法8. 验证表单完整版8.1 Html表单8.2 表单验证js逻辑8.3 表单验证css样式 1. 写在前面 我们知道&#x…

windows11经常断网WiFi

解决方法&#xff1a;从官方网站下载&#xff0c;更新WiFi驱动程序&#xff0c;

Linux:apache优化(2)—— 网页传输压缩

网页传输压缩 客户端在请求httpd服务器数据&#xff0c;httpd服务器在返回数据包给客户端时&#xff0c;先对返回的数据进行压缩&#xff0c;压缩之后再传输 作用&#xff1a;配置 Apache 的网页压缩功能&#xff0c;是使用 Gzip 压缩算法来对 Apache 服务器发布的网页内容进行…

AI又进化了,AI 写代码工具

今年 AI 的发展可谓一日千里&#xff0c;相信不少同学应该都用过 AI 来帮助自己提高开发效率吧&#xff1f; 比如让 AI 根据注释生成代码、解释整段代码、提供技术问题的答疑、修改 Bug、生成单元测试等等。 在 12 月 28 日刚刚结束的 WAVE SUMMIT 深度学习开发者大会上&…

STM32CubeMX教程8 TIM 通用定时器 - 输出比较

目录 1、准备材料 2、实验目标 3、实验流程 3.0、前提知识 3.1、CubeMX相关配置 3.1.1、时钟树配置 3.1.2、外设参数配置 3.1.3、外设中断配置 3.2、生成代码 3.2.1、外设初始化函数调用流程 3.2.2、外设中断函数调用流程 3.2.3、添加其他必要代码 4、常用函数 5…

Mysql 容易忘的 sql 指令总结

目录 一、操作数据库的基本指令 二、查询语句的指令 1、基本查询语句 2、模糊查询 3、分支查询 4、 分组查询 5、分组查询 6、基本查询总结&#xff1a; 7、子查询 8、连接查询 三、MySQL中的常用函数 1、时间函数 2、字符串函数 3、聚合函数 4、运算函数 四、表…

Leetcode 63 不同路径 II

题意理解&#xff1a; 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish”&#xff09;。 要求&#xff1a;机器人只能…

Jmeter学习总结(4)——提取接口响应内容JSON Extractor

后置提取常见的方式&#xff1a;正则表达式和JSON Extractor。 而接口响应大多是JSON格式。 在JSON提取器之前&#xff0c;可以根据响应结果去编写所需要的JSON表达式&#xff0c;在结果树中选择JSON PATH TESTER。 {"server_time": 1232333333333,"data&quo…

基于ssm的4S店预约保养系统开发+vue论文

目 录 目 录 I 摘 要 III ABSTRACT IV 1 绪论 1 1.1 课题背景 1 1.2 研究现状 1 1.3 研究内容 2 2 系统开发环境 3 2.1 vue技术 3 2.2 JAVA技术 3 2.3 MYSQL数据库 3 2.4 B/S结构 4 2.5 SSM框架技术 4 3 系统分析 5 3.1 可行性分析 5 3.1.1 技术可行性 5 3.1.2 操作可行性 5 3…

双语!性能优越|融合黏菌和差分变异的量子哈里斯鹰算法SDMQHHO

前面的文章里卡卡介绍了哈里斯鹰优化算法(Harris Hawks Optimization, HHO).HHO是 Heidari等[1]于2019年提出的一种新型元启发式算法&#xff0c;设计灵感来源于哈里斯鹰在捕食猎物过程中的合作行为以及突然袭击的狩猎风格&#xff0c;具有需调参数少、原理简单易实现、局部搜索…

Spring AOP<一>简介与基础使用

spring AOP 基础定义 含义使用切面组织多个Advice,Advice放在切面中定义。也就是说是定义通知的自定义类。自定义的AOP类Aspect连接点方法调用&#xff0c;异常抛出可以增强的点JoinPoint &#xff1a;也就是**被增强的方法的总称&#xff0c;可以获取具体方法的信息&#xff…

(2023,3D NeRF,无图像变分分数蒸馏,单步扩散)SwiftBrush:具有变分分数蒸馏的一步文本到图像扩散模型

SwiftBrush : One-Step Text-to-Image Diffusion Model with Variational Score Distillation 公众&#xff1a;EDPJ&#xff08;添加 VX&#xff1a;CV_EDPJ 或直接进 Q 交流群&#xff1a;922230617 获取资料&#xff09; 目录 0. 摘要 1. 方法 1.1 基础 1.2 SwiftBrus…

图像分割实战-系列教程2:Unet系列算法

图像分割实战-系列教程 总目录 语义分割与实例分割概述 Unet系列算法 1、Unet 整体结构&#xff1a;概述就是编码解码过程简单但是很实用&#xff0c;应用广起初是做医学方向&#xff0c;现在也是 语义分割与实例分割概述 Unet系列算法

MYSQL 深入探索系列六 SQL执行计划

概述 好久不见了&#xff0c;近期一直在忙项目的事&#xff0c;才有时间写博客&#xff0c;近期频繁出现sql问题&#xff0c;今天正好不忙咱们看看千万级别的表到底该如何优化sql。 案例 近期有个小伙伴生产环境收到了告警&#xff0c;有个6千万的日志表&#xff0c;查询耗时大…

unity学习笔记----游戏练习0

一、修复植物种植的问题 1.当手上存在植物时&#xff0c;再次点击卡片上的植物就会在手上添加新的植物&#xff0c;需要修改成只有手上没有植物时才能再次获取到植物。需要修改AddPlant方法。 public bool AddPlant(PlantType plantType) { //防止手上出现多个植…