代码随想录算法训练营Day55 ||leetCode 583. 两个字符串的删除操作 || 72. 编辑距离

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

这道题的状态方程比上一题简单一些

初始化如下

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. 编辑距离 

首先确认状态方程

如果第i位与第j位相同,那本次可以不用操作,dp[i][j]=dp[i-1][j-1]

如果不同,则需要增删改的操作,而增和删本质是等效的,对一个字符串删等于对另一个字符串加,所以取dp[i-1][j]和dp[i][j-1]的最小值+1。改的话则是dp[i-1][j-1]+1;取他们的最小值。

初始化则为

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()];}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Kafka生产者相关概念

文章目录 Kafka工作流程Kafka文件存储生产者分区策略生产者ISR生产者ack机制数据一致性问题ExactlyOnce Kafka工作流程 Kafka中消息是以topic进行分类的&#xff0c;Producer生产消息&#xff0c;Consumer消费消息&#xff0c;都是面向topic的。 Topic是逻辑上的概念&#xff…

Qt 压缩/解压文件

前面讲了很多Qt的文件操作&#xff0c;文件操作自然就包括压缩与解压缩文件了&#xff0c;正好最近项目里要用到压缩以及解压缩文件&#xff0c;所以就研究了一下Qt如何压缩与解压缩文件。 QZipReader/QZipWriter QZipReader 和 QZipWriter 类提供了用于读取和写入 ZIP 格式文…

SpringCloud Gateway工作流程

Spring Cloud Gateway的工作流程 具体的流程&#xff1a; 用户发送请求到网关 请求断言&#xff0c;用户请求到达网关后&#xff0c;由Gateway Handler Mapping&#xff08;网关处理器映射&#xff09;进行Predicates&#xff08;断言&#xff09;&#xff0c;看一下哪一个符合…

2024年C语言最新经典面试题汇总(11-20)

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…

深度学习 线性神经网络(线性回归 从零开始实现)

介绍&#xff1a; 在线性神经网络中&#xff0c;线性回归是一种常见的任务&#xff0c;用于预测一个连续的数值输出。其目标是根据输入特征来拟合一个线性函数&#xff0c;使得预测值与真实值之间的误差最小化。 线性回归的数学表达式为&#xff1a; y w1x1 w2x2 ... wnxn …

LeetCode每日一题——统计桌面上的不同数字

统计桌面上的不同数字OJ链接&#xff1a;2549. 统计桌面上的不同数字 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 思路&#xff1a; 这是一个很简单的数学问题&#xff1a; 当n 5时&#xff0c;因为n % 4 1&#xff0c;所以下一天4一定会被放上桌面 当n 4…

TnT-LLM: Text Mining at Scale with Large Language Models

TnT-LLM: Text Mining at Scale with Large Language Models 相关链接&#xff1a;arxiv 关键字&#xff1a;Large Language Models (LLMs)、Text Mining、Label Taxonomy、Text Classification、Prompt-based Interface 摘要 文本挖掘是将非结构化文本转换为结构化和有意义的…

QT(C++)-error LNK2038: 检测到“_ITERATOR_DEBUG_LEVEL”的不匹配项: 值“2”不匹配值“0”

1、项目场景&#xff1a; 在VS中采用QT&#xff08;C&#xff09;调试时&#xff0c;出现error LNK2038: 检测到“_ITERATOR_DEBUG_LEVEL”的不匹配项: 值“2”不匹配值“0”错误 2、解决方案&#xff1a; 在“解决方案资源管理器”中选中出现此类BUG的项目&#xff0c;右键-…

【NLP笔记】预训练+微调范式之OpenAI Transformer、ELMo、ULM-FiT、Bert..

文章目录 OpenAI TransformerELMoULM-FiTBert基础结构Embedding预训练&微调 【原文链接】&#xff1a; BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding 【本文参考链接】 The Illustrated BERT, ELMo, and co. (How NLP Cracked Tra…

提面 | 面试抽题

学习到更新日期面试抽题-1.2案例分析的思维本质2024-3-23 1提面抽屉论述问题的分类 1.1案例分析占总论 1.2案例分析的思维本质

计算机网络相关

OSI七层模型 各层功能&#xff1a; TCP/IP四层模型 应用层 传输层 网络层 网络接口层 访问一个URL的全过程 在浏览器中输入指定网页的 URL。 浏览器通过 DNS 协议&#xff0c;获取域名对应的 IP 地址。 浏览器根据 IP 地址和端口号&#xff0c;向目标服务器发起一个 TCP…

【进阶五】Python实现SDVRP(需求拆分)常见求解算法——离散粒子群算法(DPSO)

基于python语言&#xff0c;采用经典离散粒子群算法&#xff08;DPSO&#xff09;对 需求拆分车辆路径规划问题&#xff08;SDVRP&#xff09; 进行求解。 目录 往期优质资源1. 适用场景2. 代码调整3. 求解结果4. 代码片段参考 往期优质资源 经过一年多的创作&#xff0c;目前已…

linux文本三剑客 --- grep、sed、awk

1、grep grep&#xff1a;使用正则表达式搜索文本&#xff0c;将匹配的行打印出来&#xff08;匹配到的标红&#xff09; 命令格式&#xff1a;grep [option] pattern file <1> 命令参数 -A<显示行数>&#xff1a;除了显示符合范本样式的那一列之外&#xff0c;并…

C语言中的联合体和枚举

联合体 联合体的创建 联合体的关键字是union union S {char a;int i; };除了关键字和结构体不一样之外&#xff0c;联合体的创建语法形式和结构体的很相似&#xff0c;如果不熟悉结构体的创建&#xff0c;可以看一下我上一篇的博客关于结构体知识的详解。 联合体的特点 联合…

Personal Website

Personal Website Static Site Generators hexo hugo jekyll Documentation Site Generator gitbook vuepress vitepress docsify docute docusaurus Deployment 1. GitHub Pages 2. GitLab Pages 3. vercel 4. netlify Domain 域名注册 freessl 域名解析域名…

【GUI】自动化办公

目录 一、GUI介绍 二、环境安装 三、鼠标移动操作 四、鼠标点击操作 五、拖动鼠标 六、鼠标滚动操作 七、屏幕快照&图像识别基础 7.1 屏幕快照&#xff08;截图&#xff09; 7.2 图像识别 八、键盘控制 一、GUI介绍 GUI自动化就是写程序直接控制键盘和鼠标。这些…

电脑如何关闭自启动应用?cmd一招解决问题

很多小伙伴说电脑刚开机就卡的和定格动画似的&#xff0c;cmd一招解决问题&#xff1a; CtrlR打开cmd,输入&#xff1a;msconfig 进入到这个界面&#xff1a; 点击启动&#xff1a; 打开任务管理器&#xff0c;禁用不要的自启动应用就ok了

【prometheus-operator】k8s监控集群外redis

1、部署exporter GitHub - oliver006/redis_exporter: Prometheus Exporter for Redis Metrics. Supports Redis 2.x, 3.x, 4.x, 5.x, 6.x, and 7.x redis_exporter-v1.57.0.linux-386.tar.gz # 解压 tar -zxvf redis_exporter-v1.57.0.linux-386.tar.gz # 启动 nohup ./redi…

SpringCloud-记

目录 什么是SpringCloud 什么是微服务 SpringCloud的优缺点 SpringBoot和SpringCloud的区别 RPC 的实现原理 RPC是什么 eureka的自我保护机制 Ribbon feigin优点 Ribbon和Feign的区别 什么是SpringCloud Spring Cloud是一系列框架的有序集合。它利用Spring Boot的开发…

力扣面试150 阶乘后的零 数论 找规律 质因数

Problem: 172. 阶乘后的零 思路 &#x1f468;‍&#x1f3eb; 大佬神解 一个数末尾有多少个 0 &#xff0c;取决于这个数 有多少个因子 10而 10 可以分解出质因子 2 和 5而在阶乘种&#xff0c;2 的倍数会比 5 的倍数多&#xff0c;换而言之&#xff0c;每一个 5 都会找到一…