算法工程师重生之第三十九天（不同的子序列 两个字符串的删除操作 编辑距离 编辑距离总结篇 ）

参考文献 代码随想录

一、不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

  • 1 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成

暴力回溯（超时）

class Solution(object):def __init__(self):self.result = 0def numDistinct(self, s, t):""":type s: str:type t: str:rtype: int"""self.dfs(s, t, '', 0)return self.resultdef dfs(self, s, t, li, startIndex):if li == t:self.result += 1for i in range(startIndex, len(s)):self.dfs(s, t, li + s[i], i + 1)

动规

class Solution(object):def numDistinct(self, s, t):""":type s: str:type t: str:rtype: int"""n, m = len(s), len(t)# 创建 DP 表以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]#我们求的是 s 中有多少个 t，而不是 求t中有多少个s，所以只考虑 s中删除元素的情况，即 不用s[i - 1]来匹配 的情况。dp = [[0] * (m + 1) for _ in range(n + 1)]# 当 t 为空字符串时，s 的所有子串都可以形成空字符串for i in range(n + 1):dp[i][0] = 1# 填充 DP 表for i in range(1, n + 1):for j in range(1, m + 1):if s[i - 1] == t[j - 1]:  # 相等的时候dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]else:dp[i][j] = dp[i - 1][j]return dp[n][m]

三、两个字符串的删除操作

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

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

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例  2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

  • 1 <= word1.length, word2.length <= 500
  • word1 和 word2 只包含小写英文字母
class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""n = len(word1)m = len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]  # 代表的是i-1word2，j-1word1相同操作最少的次数for i in range(n + 1):  #有一个是空字符串，另外一个不是，另外一个字符串有多长，那么就要删除多少次dp[0][i] = ifor j in range(m + 1):dp[j][0] = jfor i in range(1, m + 1):for j in range(1, n + 1):if word1[j - 1] == word2[i - 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[-1][-1]

求出最长的公共子序列，然后在用2个字符串的长度减去最长的2倍

class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""n = len(word1)m = len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]  # 代表的是i-1word2，j-1word1相同操作最少的次数# for i in range(n + 1):  #有一个是空字符串，另外一个不是，另外一个字符串有多长，那么就要删除多少次#     dp[0][i] = i# for j in range(m + 1):#     dp[j][0] = jresult = 0for i in range(1, m + 1):for j in range(1, n + 1):if word1[j - 1] == word2[i - 1]:  # 如果当前字符相等，那么就依赖前一个字符dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])result = max(result, dp[i][j])return (n + m) - 2 * result

三、编辑距离

给你两个单词 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(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""n = len(word1)m = len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]  # dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。for i in range(n + 1):  #有一个是空字符串，另外一个不是，另外一个字符串有多长，那么就要删除多少次dp[0][i] = ifor j in range(m + 1):dp[j][0] = jfor i in range(1, m + 1):for j in range(1, n + 1):if word1[j - 1] == word2[i - 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] + 1)return dp[-1][-1]

四、编辑距离总结篇

判断子序列

动态规划：392.判断子序列 (opens new window)给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

这道题目 其实是可以用双指针或者贪心的的，但是我在开篇的时候就说了这是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。

  • if (s[i - 1] == t[j - 1])
    • t中找到了一个字符在s中也出现了
  • if (s[i - 1] != t[j - 1])
    • 相当于t要删除元素，继续匹配

状态转移方程：

if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];

#不同的子序列

动态规划：115.不同的子序列 (opens new window)给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

本题虽然也只有删除操作，不用考虑替换增加之类的，但相对于动态规划：392.判断子序列 (opens new window)就有难度了，这道题目双指针法可就做不了。

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。

一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

这里可能有同学不明白了，为什么还要考虑 不用s[i - 1]来匹配，都相同了指定要匹配啊。

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]

所以递推公式为：dp[i][j] = dp[i - 1][j];

状态转移方程：

if (s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {dp[i][j] = dp[i - 1][j];
}

#两个字符串的删除操作

动态规划：583.两个字符串的删除操作 (opens new window)给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最少步数，每步可以删除任意一个字符串中的一个字符。

本题和动态规划：115.不同的子序列 (opens new window)相比，其实就是两个字符串可以都可以删除了，情况虽说复杂一些，但整体思路是不变的。

  • 当word1[i - 1] 与 word2[j - 1]相同的时候
  • 当word1[i - 1] 与 word2[j - 1]不相同的时候

当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

状态转移方程：

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] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
}

#编辑距离

动态规划：72.编辑距离 (opens new window)给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

编辑距离终于来了，有了前面三道题目的铺垫，应该有思路了，本题是两个字符串可以增删改，比 动态规划：判断子序列 (opens new window)，动态规划：不同的子序列 (opens new window)，动态规划：两个字符串的删除操作 (opens new window)都要复杂的多。

在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：

  • if (word1[i - 1] == word2[j - 1])
    • 不操作
  • if (word1[i - 1] != word2[j - 1])
    • 增
    • 删
    • 换

也就是如上四种情况。

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

此时可能有同学有点不明白，为啥要即dp[i][j] = dp[i - 1][j - 1]呢？

那么就在回顾上面讲过的dp[i][j]的定义，word1[i - 1] 与 word2[j - 1]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1] 就是 dp[i][j]了。

在下面的讲解中，如果哪里看不懂，就回想一下dp[i][j]的定义，就明白了。

在整个动规的过程中，最为关键就是正确理解dp[i][j]的定义！

if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

操作一：word1增加一个元素，使其word1[i - 1]与word2[j - 1]相同，那么就是以下标i-2为结尾的word1 与 i-1为结尾的word2的最近编辑距离 加上一个增加元素的操作。

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

操作二：word2添加一个元素，使其word1[i - 1]与word2[j - 1]相同，那么就是以下标i-1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个增加元素的操作。

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

这里有同学发现了，怎么都是添加元素，删除元素去哪了。

word2添加一个元素，相当于word1删除一个元素，例如 word1 = "ad" ，word2 = "a"，word2添加一个元素d，也就是相当于word1删除一个元素d，操作数是一样！

操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。

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

综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

递归公式代码如下：

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;
}

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

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

相关文章

Atlas800昇腾服务器（型号：3000）—SwinTransformer等NPU推理【图像分类】（九）

Atlas800昇腾服务器（型号：3000）—SwinTransformer等NPU推理【图像分类】（九）

服务器配置如下&#xff1a; CPU/NPU&#xff1a;鲲鹏 CPU&#xff08;ARM64&#xff09;A300I pro推理卡 系统&#xff1a;Kylin V10 SP1【下载链接】【安装链接】 驱动与固件版本版本&#xff1a; Ascend-hdk-310p-npu-driver_23.0.1_linux-aarch64.run【下载链接】 Ascend-…
阅读更多...
14. NSWindow 窗口与 NSWindowController 窗口控制器

14. NSWindow 窗口与 NSWindowController 窗口控制器

NSWindowController窗口控制器主要用于管理xib/storyboard文件中加载的NSWindow对象&#xff1a;1、创建一个基于xib或storyboard的NSWindowController子类会自动创建一个NSWindow&#xff1b;2、如果手工创建NSWindow对象&#xff0c;则需要维护NSWindowController和NSWindow之…
阅读更多...
02 什么是Babel

02 什么是Babel

什么是Babel&#xff1f; Babel 是一个 JavaScript 编译器,提供了JavaScript的编译过程&#xff0c;能够将源代码转换为目标代码。AST -> Transform -> Generate 官网 Babel Babel 查看AST https://astexplorer.net/ Babel所有的包 babel/traverse Babel Babel 是…
阅读更多...
【论文阅读笔记】VLP: A Survey on Vision-language Pre-training

【论文阅读笔记】VLP: A Survey on Vision-language Pre-training

目录 前言2 特征提取&#xff08;Feature extraction&#xff09;2.1.1 图象特征提取OD-based Region feature / RoIFreeze the pre-trained object detectorsGrid features&#xff08;网格特征&#xff09;CNN-GFsEnd-to-End Training&#xff08;端到端训练&#xff09;ViT-…
阅读更多...
TortoiseSVN小乌龟下载安装（Windows11）

TortoiseSVN小乌龟下载安装（Windows11）

目录 TortoiseSVN 1.14.7工具下载安装 TortoiseSVN 1.14.7 工具 系统&#xff1a;Windows 11 下载 官网&#xff1a;https://tortoisesvn.subversion.org.cn/downloads.html如图选 TortoiseSVN 1.14.7 - 64 位 下载完成 安装 打开 next&#xff0c;next Browse&#xf…
阅读更多...
Mac OS 搭建MySQL开发环境

Mac OS 搭建MySQL开发环境

Mac OS 搭建MySQL开发环境 文章目录 Mac OS 搭建MySQL开发环境一、安装Mysql&#xff1a;二、配置环境变量三、安装Navicat 本地环境&#xff1a; Mac OS Sequoia15.0.1&#xff08;M3 Max) 目标状态&#xff1a; 下载安装Mysql&#xff0c;配置相关环境。 一、安装Mysql&…
阅读更多...
docker Desktop开启远程访问端口

docker Desktop开启远程访问端口

文章目录 问题解决方法1.首先开启docker Desktop的访问端口2.将本地端口绑定远程访问ip 验证 问题 Windows上部署的docker&#xff0c;没办法通过远程的ip进行访问&#xff0c;实现远程代码的部署。 解决方法 1.首先开启docker Desktop的访问端口 通过开启docker访问端口&am…
阅读更多...
Linux文件系统学习（未完）

Linux文件系统学习（未完）

1. Linux文件系统的特点与类别 1.1 特点 Linux系统中&#xff0c;文件组织在一个统一的树形目录结构中&#xff0c;整个文件系统有一个根“/”&#xff08;文件夹&#xff09;&#xff0c;然后以每个目录&#xff08;文件夹&#xff09;作为分叉&#xff0c;叶子节点作为文件…
阅读更多...
Three.js 快速入门构建你的第一个 3D 应用

Three.js 快速入门构建你的第一个 3D 应用

![ 开发领域&#xff1a;前端开发 | AI 应用 | Web3D | 元宇宙 技术栈&#xff1a;JavaScript、React、Three.js、WebGL、Go 经验经验&#xff1a;6年 前端开发经验&#xff0c;专注于图形渲染和AI技术 开源项目&#xff1a;github 晓智元宇宙、数字孪生引擎、前端面试题 大家好…
阅读更多...
排序算法汇总

排序算法汇总

一、二分查找 public static int binarySearch(int[] nums,int target){int l 0, r nums.length-1;while(l < r){int mid l (r-l)/2;if(nums[mid] target){return mid;}else if(nums[mid] < target){r mid - 1;}else{l mid 1;}}return -1;} 对于防止溢出的 mid …
阅读更多...
类和对象（2）

类和对象（2）

1.类的默认成员函数 默认成员函数就是⽤⼾没有显式实现&#xff0c;编译器会⾃动⽣成的成员函数称为默认成员函数。⼀个类&#xff0c;我们不写的情况下编译器会默认⽣成以下6个默认成员函数&#xff0c;需要注意的是这6个中最重要的是前4个&#xff0c;最后两个取地址重载不…
阅读更多...
AcWing 1303：斐波那契前 n 项和 ← 矩阵快速幂加速递推

AcWing 1303：斐波那契前 n 项和 ← 矩阵快速幂加速递推

【题目来源】https://www.acwing.com/problem/content/1305/http://poj.org/problem?id3070【题目描述】 大家都知道 数列吧&#xff0c;。现在问题很简单&#xff0c;输入 和 &#xff0c;求 的前 项和 。【输入格式】 共一行&#xff0c;包含两个整数 和 。【输出格式】…
阅读更多...
ElasticSearch备考 -- Index rollover

ElasticSearch备考 -- Index rollover

一、题目 给索引my-index-000001&#xff0c;创建别名my-index&#xff0c;并设置rollover&#xff0c;满足以下三个条件的 The index was created 7 or more days ago.The index contains 5 or more documents.The index’s largest primary shard is 1GB or larger. 二、思考…
阅读更多...
zabbix 6.0 监控clickhouse(单机）

zabbix 6.0 监控clickhouse(单机）

zabbix 6.0 LTS已经包含了clickhouse的监控模板&#xff0c;所以我们可以直接使用自带的模板来监控clickhouse了。 0.前置条件 clickhouse 已经安装&#xff0c;我安装的是24.3.5.47zabbix-agent 已经安装并配置。系统是ubuntu 2204 server 1. 新建监控用户 使用xml的方式为…
阅读更多...
Jmeter自动化实战

Jmeter自动化实战

一、前言 由于系统业务流程很复杂,在不同的阶段需要不同的数据,且数据无法重复使用,每次造新的数据特别繁琐,故想着能不能使用jmeter一键造数据 二、创建录制模板 可参考:jmeter录制接口 首先创建一个录制模板 因为会有各种请求头,cookies,签名,认证信息等原因,导致手动复制…
阅读更多...
提升网站速度与性能优化的有效策略与实践

提升网站速度与性能优化的有效策略与实践

内容概要 在数字化快速发展的今天&#xff0c;网站速度与性能优化显得尤为重要&#xff0c;它直接影响用户的浏览体验。用户在访问网站时&#xff0c;往往希望能够迅速获取信息&#xff0c;若加载时间过长&#xff0c;轻易可能导致他们转向其他更为流畅的网站。因此&#xff0…
阅读更多...
OpenCV视觉分析之目标跟踪(6)轻量级目标跟踪器类TrackerNano的使用

OpenCV视觉分析之目标跟踪(6)轻量级目标跟踪器类TrackerNano的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 Nano 跟踪器是一个超轻量级的基于深度神经网络&#xff08;DNN&#xff09;的通用目标跟踪器。 由于特殊的模型结构&#xff0c;Nano 跟踪器速度…
阅读更多...
C数组手动输入问题

C数组手动输入问题

问题界面 解析 输入数组数据也需要加取地址符吗&#xff1f;数组不就是地址了吗&#xff1f; 理解array[i]和array[i][j]的区别&#xff1a; array[i]是一个指向第i行第一个元素的指针&#xff08;int*类型&#xff0c;指向array[i][0]&#xff09;。 array[i][j]是一个int类…
阅读更多...
Hadoop-002-部署并配置HDFS集群

Hadoop-002-部署并配置HDFS集群

集群规划 Hadoop HDFS的角色包含 NameNode(主节点管理者)、DataNode(从节点工作者)、SeconddaryNameNode(从节点辅助) 节点CPU内存hadoop-11C4Ghadoop-21C2Ghadoop-31C2G 一、下载上传Hadoop包 注意: 登录hadoop-1节点root用户执行 1、官网下载安装包后上传 到hadoop-1服务…
阅读更多...
Android 在github网站下载项目：各种很慢怎么办？比如gradle下载慢；访问github慢；依赖下载慢

Android 在github网站下载项目：各种很慢怎么办？比如gradle下载慢；访问github慢；依赖下载慢

目录 访问github慢gradle下载慢依赖下载慢 前言 大家好&#xff0c;我是前期后期&#xff0c;在网上冲浪的一名程序员。 为什么要看这篇文章呢&#xff1f;问题是什么&#xff1f; 我们在Github上面看到一些好的项目的时候&#xff0c;想下载下来研究学习一下。但经常遇到各…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023