代码随想录算法训练营第五十五天|动态规划|583. 两个字符串的删除操作 、72. 编辑距离、 编辑距离总结篇

本文主要是介绍代码随想录算法训练营第五十五天|动态规划|583. 两个字符串的删除操作 、72. 编辑距离、 编辑距离总结篇,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

583. 两个字符串的删除操作

文章

给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。

示例:

输入: “sea”, “eat”
输出: 2
解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); j++) {if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[word1.size()][word2.size()];}
};

72. 编辑距离

文章
给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符

删除一个字符

替换一个字符

示例 1:

输入:word1 = “horse”, word2 = “ros”

输出:3

解释: horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

示例 2:

输入:word1 = “intention”, word2 = “execution”

输出:5

解释: intention -> inention (删除 ‘t’) inention -> enention (将 ‘i’ 替换为 ‘e’) enention -> exention (将 ‘n’ 替换为 ‘x’) exention -> exection (将 ‘n’ 替换为 ‘c’) exection -> execution (插入 ‘u’)

提示:

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成


class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); j++) {if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];}else {dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;}}}return dp[word1.size()][word2.size()];}
};

这篇关于代码随想录算法训练营第五十五天|动态规划|583. 两个字符串的删除操作 、72. 编辑距离、 编辑距离总结篇的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/843318

相关文章

Django开发时如何避免频繁发送短信验证码(python图文代码)

《Django开发时如何避免频繁发送短信验证码(python图文代码)》Django开发时,为防止频繁发送验证码,后端需用Redis限制请求频率,结合管道技术提升效率,通过生产者消费者模式解耦业务逻辑... 目录避免频繁发送 验证码1. www.chinasem.cn避免频繁发送 验证码逻辑分析2. 避免频繁

精选20个好玩又实用的的Python实战项目(有图文代码)

《精选20个好玩又实用的的Python实战项目(有图文代码)》文章介绍了20个实用Python项目,涵盖游戏开发、工具应用、图像处理、机器学习等,使用Tkinter、PIL、OpenCV、Kivy等库... 目录① 猜字游戏② 闹钟③ 骰子模拟器④ 二维码⑤ 语言检测⑥ 加密和解密⑦ URL缩短⑧ 音乐播放

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作:数据读取与查看3. 索引操作:精准定位数据4. Group

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

MySQL常用字符串函数示例和场景介绍

《MySQL常用字符串函数示例和场景介绍》MySQL提供了丰富的字符串函数帮助我们高效地对字符串进行处理、转换和分析,本文我将全面且深入地介绍MySQL常用的字符串函数,并结合具体示例和场景,帮你熟练... 目录一、字符串函数概述1.1 字符串函数的作用1.2 字符串函数分类二、字符串长度与统计函数2.1

Python操作PDF文档的主流库使用指南

《Python操作PDF文档的主流库使用指南》PDF因其跨平台、格式固定的特性成为文档交换的标准,然而,由于其复杂的内部结构,程序化操作PDF一直是个挑战,本文主要为大家整理了Python操作PD... 目录一、 基础操作1.PyPDF2 (及其继任者 pypdf)2.PyMuPDF / fitz3.Fre

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali

MySQL 强制使用特定索引的操作

《MySQL强制使用特定索引的操作》MySQL可通过FORCEINDEX、USEINDEX等语法强制查询使用特定索引,但优化器可能不采纳,需结合EXPLAIN分析执行计划,避免性能下降,注意版本差异... 目录1. 使用FORCE INDEX语法2. 使用USE INDEX语法3. 使用IGNORE IND

C# $字符串插值的使用

《C#$字符串插值的使用》本文介绍了C#中的字符串插值功能,详细介绍了使用$符号的实现方式,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录$ 字符使用方式创建内插字符串包含不同的数据类型控制内插表达式的格式控制内插表达式的对齐方式内插表达式中使用转义序列内插表达式中使用

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到