力扣● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 编辑距离总结篇

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

注意审题:

给定两个单词 word1 和 word2 ,返回使得 word1 和  word2 相同所需的最小步数

每步 可以删除任意一个字符串中的一个字符。

删除最少的字符使两者相同,说明留下来的就是最大公共子序列。不要求连续,所以可以使用● 1143.最长公共子序列 来做,最长公共子序列之外的字母都要删除,所以返回 (n1+n2-2*dp[n1][n2]) 即可。

这是间接求法,直接求:

1.dp数组含义。

dp[i][j]:以word1[i-1]为结尾的字符串,和以word2[j-1]位结尾的字符串,想要达到相等,所需要删除元素的最少次数为dp[i][j]。

2.递推公式。

如果相等:删除次数要最少,那么相等的话就不能删除,得留着,所以dp[i][j]=dp[i-1][j-1];

如果不等:2个字符串没有谁长谁短的前提,所以应该有3种情况。

①可能删掉word1[i-1],那么dp[i][j]代表的子序列和dp[i-1][j]代表的子序列删除的字母,就多了一个:word1[i-1],所以dp[i][j]=dp[i-1][j]+1;

②可能删掉word2[j-1],同样,dp[i][j]=dp[i][j-1]+1;

③都删除。都删除的话,dp[i][j]代表的子序列和dp[i-1][j-1]代表的子序列删除的字母,就多了2个:word1[i-1]和word2[j-1],所以是dp[i][j]=dp[i-1][j-1]+2;这其实也是满足情况①和情况②的,删掉2个,和dp[i-1][j]相比多删了一个word2[j-1],和dp[i][j-1]相比多删了一个word1[i-1]。所以情况①/情况②就把③包含了。所以只取①和②的最小删除数量,即Min值就是对的。

dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);

3.初始化。

dp[i][0]。i>0时,word1[i-1]:非空串;word2[0,-1]:空串。所以应该删除word1的前i个达到相等。

dp[0][j]。同样应该删除word2的前j个达到相等。

dp[0][0]。不用删除,=0。

4.遍历顺序。

5.打印。

代码如下:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
        for(int i=1;i<=n1;++i)dp[i][0]=i;
        for(int j=1;j<=n2;++j)dp[0][j]=j;
        for(int i=1;i<=n1;++i){
            for(int j=1;j<=n2;++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);//省略dp[i-1][j-1]+2;
                }
            }
        }
        return dp[n1][n2];
    }
};


● 72. 编辑距离

1.dp数组含义。

dp[i][j]:数组1[0,i-1]中操作(插删换)dp[i][j]次,得到的序列是数组2[0,j-1]。注意这个操作过程是可逆的,2[0,j-1]中操作(删插换)dp[i][j]次,得到的序列是1[0,i-1]。

所以每一步操作,既可以对数组1操作,也可以对数组2操作。我觉得变换一下题目解法也没有变:请返回操作后使word1和word2相同的最大操作数。

举例:“horse”变成“ros”:

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

因为,对数组1 的 插入 等同于对数组2 的删除,删除同理,那么:

ros -> rose (插入 'e');horse-> rorse(将 'h' 替换为 'r');rose -> rorse(插入 'r')。

即中间每步可以选择对1操作,也可以对2操作。可见操作后可以得到很多种相同字符串(horse、rorse、rose或ros),但是过程中数组1和数组2操作的次数之和是固定的,即编辑距离是固定的。

2.递推公式。

(1)不相等的话,这3个操作都有可能发生,那么是肯定要加上1(做一个操作)。

①替换:

可以1[i-1]替换成2[j-1],也可以2[j-1]替换成1[i-1]。改了之后,得到的2个子数组最后元素相同,所以应该是在dp[i-1][j-1]的基础上替换了1或2的一个元素,所以+1。

即dp[i][j]=dp[i-1][j-1]+1。

②可以删除:

删除1[i-1]达到相同,说明[0,i-2]中操作之后,就能得到2[0,j-1]了,所以是在这个基础(dp[i-1][j])之上加一个删除操作即可,即dp[i][j]=dp[i-1][j]+1。

也可以删除2[j-1]达到相同,那么同理,dp[i][j]=dp[i][j-1]+1。

③可以插入:

插入1[i-1]达到相同,代表着删除2[i-1]达到相同,上面说了只是操作不同但次数相同,所以在1或2插入的情况都可以用删除表示,所以1[i-1]后面插入的情况下dp[i][j]==dp[i][j-1]+1。2[j-1]后面插入的情况下dp[i][j]=dp[i-1][j]+1。上面都包含了。

所以:dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;

(2)相等:和上题同样是求最少操作数,所以相等的话不操作,即dp[i][j]=dp[i-1][j-1]。

3.初始化。

回忆dp的含义:

dp[i][0]=i。以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]。

dp[0][j]=j。同理。

4.遍历顺序。

从上到下,从左到右。

5.打印。

代码如下:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
        for(int j=0;j<=n2;++j)dp[0][j]=j;//删除
        for(int i=0;i<=n1;++i)dp[i][0]=i;//插入
        for(int i=1;i<=n1;++i){
            for(int j=1;j<=n2;++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],min(dp[i-1][j],dp[i][j-1]))+1;//,
                }
            }
        }
        return dp[n1][n2];
    }
};


● 编辑距离总结篇   

做多了总结一下:都是在dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]的基础上得到dp[i][j],要得到这个递推公式,就是得清楚,什么情况下,对A[i-1](B[j-1])做什么操作,比如上面● 72. 编辑距离,不相同的话,可能对A[i-1]和B[j-1]这一对,修改其中一个就行,所以是在dp[i-1][j-1]基础上+1……

总结一下3个编辑距离前导题:

判断子序列

不同的子序列

两个字符串的删除操作

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

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

相关文章

01.Vue2入门

一、为什么要学习Vue 1.前端必备技能 2.岗位多&#xff0c;绝大互联网公司都在使用Vue 3.提高开发效率 4.高薪必备技能&#xff08;Vue2Vue3&#xff09; 二、什么是Vue 概念&#xff1a;Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套 **构建用户界面 ** 的 渐进式 …

多种双拼方案的实现

首发日期 2024-03-14, 以下为原文内容: 就像 GNU/Linux 用户, 虽然比例小, 却又分散为一堆不同的发行版. 双拼用户在拼音输入法之中的比例也很小, 同时也分为各种不同的双拼方案. 那么作为一个 双拼 输入法, 最重要的事情是什么呢 ? 嗯, 那当然是支持自定义双拼方案 ! 实际上…

网络协议与层次划分:探索计算机网络体系结构

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

AWTK slider_circle 控件发布

slider_circle 控件。 主要特色&#xff1a; 支持正向和反向支持设置滑块的半径支持背景线宽和颜色支持前景线宽和颜色支持设置是否显示值的文本支持设置起始角度和结束角度支持设置格式化值的格式字符串支持使用图片填充背景和前景 界面效果&#xff1a; 注意&#xff1a; …

【绘图案例-绘图的方式1 Objective-C语言】

一、接下来,我们来说这个,绘图的方式 1.新建一个项目,Name:04-绘图的方式, 方式:就是,我要同样画一条线,然后,用不同的代码,把它写出来,这就叫方式, 我们在storyboard里边,还拖一个UIView,这些步骤都一样, 我们来一个,宽= 300, 高 = 300 , 然后,再来一个水…

zabbix配置

1 下载zabbix 1 配置yum源 rpm -Uvh https://repo.zabbix.com/zabbix/5.0/rhel/7/x86_64/zabbix-release- 5.0-1.el7.noarch.rpm yum clean all yum makecache fast 完成后会出现zabbix.repo文件 2安装zabbix服务 yum -y install zabbix-server-mysql zabbix-web-mysql z…

计算机网络——物理层(信道复用技术)

计算机网络——物理层&#xff08;信道复用技术&#xff09; 信道复用技术频分多址与时分多址 频分复用 FDM (Frequency Division Multiplexing)时分复用 TDM (Time Division Multiplexing)统计时分复用 STDM (Statistic TDM)波分复用码分复用 我们今天接着来看信道复用技术&am…

20W-50W厚膜无感电阻TO-220封装技术规格散热说明

EAK为设计工程师提供了一种开放式屏蔽基板器件&#xff0c;用于需要卓越热性能的应用&#xff0c;开发了一种额定功率高达 50W 的厚膜功率电阻器。该电阻器采用 TO-220 开放式屏蔽基板封装&#xff0c;并具有与基板粘合的绝缘锥形文丘里管&#xff0c;以实现最大的散热。 电阻器…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:Counter)

计数器组件&#xff0c;提供相应的增加或者减少的计数操作。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 可以包含子组件。 接口 Counter() 从API version 9开始&#xff0c;该接口…

Flask 专题

[CISCN2019 总决赛 Day1 Web3]Flask Message Board 查看session解密 但不知道密钥&#xff0c;题目说FLASK,那肯定就是找密钥,发现输入什么都没有显示&#xff0c;只有author那里有回显在版上&#xff0c;所以尝试sstl&#xff0c;{{config}}找到密钥 扫目录发现有admin进入…

Python数学建模-2.5Pandas库介绍

2.5.1Pandas基本操作 Pandas是一个强大的Python数据分析库&#xff0c;它提供了快速、灵活且富有表现力的数据结构&#xff0c;设计初衷是为了处理关系型或标记型数据。Pandas的基本操作涵盖了数据的读取、处理、筛选、排序、分组、合并以及可视化等多个方面。 以下是一些Pan…

判断闰年(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int year 2000;//执行循环判断&#xff1b;while (year < 2010){//执行流程&#xff1b;//判断能否整除4&#xff1…

配置IPv4静态路由示例

配置IPv4静态路由示例 图1 配置IP静态路由组网图 组网需求配置思路操作步骤配置文件 组网需求 如图1所示&#xff0c;STA1、STA2和PC1属于不同网段&#xff0c;STA1在AP1中上线&#xff0c;STA2在AP2中上线&#xff0c;要求配置静态路由&#xff0c;使PC1与STA1和STA2能够互…

python之万花尺

1、使用模块 import sys, random, argparse import numpy as np import math import turtle import random from PIL import Image from datetime import datetime from math import gcd 依次使用pip下载即可 2、代码 import sys, random, argparse import numpy as np imp…

Yolo系列算法-理论部分-YOLOv4

0. 写在前面 YOLO系列博客&#xff0c;紧接上一篇Yolo系列算法-理论部分-YOLOv3-CSDN博客 1. YOLOv4-实战破局 2020年&#xff0c;YOLO系列的作者发表声明&#xff0c;出于道德方面的考虑&#xff0c;退出CV界&#xff0c;Alexey Bochkovskiy团队接手&#xff0c;正式推出YOLO…

财富池指标公式--通达信主力资金指标公式,主力资金流向怎么看?

今日分享的通达信主力资金指标公式&#xff0c;是一个分析主力资金进出的指标。 具体信号说明&#xff1a; 当紫色的起涨点主力资金线和红色的拉升资金同时上传0线&#xff0c;并且紫色的拉升线超过资金线&#xff0c;大盘进入派发阶段&#xff0c;后市看涨&#xff0c;是参考…

【python】成功解决使用 np.savetxt 出现ValueError: fname must be a string or file handle

【python】成功解决使用 np.savetxt 出现ValueError: fname must be a string or file handle &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入…

vue2点击左侧的树节点(el-tree)定位到对应右侧树形表格(el-table)的位置,树形表格懒加载

左侧树代码 <el-tree :data"treeData" node-key"id" default-expand-all"" //节点默认全部展开:expand-on-click-node"false" //是否在点击节点的时候展开或者收缩节点:props"defaultProps" node-click"handleNodeC…

大数据架构设计

本博客地址&#xff1a;https://security.blog.csdn.net/article/details/136657478 一. 基本概念 1、解决传统数据架构无法及时响应用户请求的常用解决方法&#xff1a; ● 增加异步处理队列&#xff0c;通过工作处理层批量处理异步处理队列中的数据修改请求。 ● 建立数据库…

uni-popup(实现自定义弹窗提示、交互)

一般提示框的样式&#xff0c;一般由设计稿而定&#xff0c;如果用uniapp的showmodel&#xff0c;那个并不能满足我们需要的自定义样式&#xff0c;所以最好的方式是我们自己封装一个&#xff01;&#xff08;想什么样就什么样&#xff09;&#xff01; 一、页面效果 二、使用…