【动态规划-最长公共子序列(LCS)】【hard】力扣1092. 最短公共超序列
给你两个字符串 str1 和 str2,返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个,则可以返回满足条件的 任意一个 答案。
如果从字符串 t 中删除一些字符(也可能不删除),可以得到字符串 s ,那么 s 就是 t 的一个子序列。
示例 1:
输入:str1 = “abac”, str2 = “cab”
输出:“cabac”
解释:
str1 = “abac” 是 “cabac” 的一个子串,因为我们可以删去 “cabac” 的第一个 "c"得到 “abac”。
str2 = “cab” 是 “cabac” 的一个子串,因为我们可以删去 “cabac” 末尾的 “ac” 得到 “cab”。
最终我们给出的答案是满足上述属性的最短字符串。
示例 2:
输入:str1 = “aaaaaaaa”, str2 = “aaaaaaaa”
输出:“aaaaaaaa”
提示:
1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。
class Solution {
public:string shortestCommonSupersequence(string str1, string str2) {int m = str1.size(), n = str2.size();vector<vector<int>> dp(m+1, vector<int>(n+1));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (str1[i - 1] == str2[j - 1]) {// 如果当前字符相等,则在前一个 LCS 的基础上加 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 否则,取前一个状态的最大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}int i = str1.size();int j = str2.size();string result = "";// 通过回溯 dp 数组来构建resultwhile (i > 0 && j > 0) {if (str1[i - 1] == str2[j - 1]) {// 如果字符相等,则是 result 的一部分result = str1[i - 1] + result;i--;j--;} else if (dp[i - 1][j] > dp[i][j - 1]) {// 如果字符不等,加入 str1 的字符result = str1[i - 1] + result;i--;} else {// 或者加入 str2 的字符result = str2[j - 1] + result;j--;}}while (i > 0) {result = str1[i - 1] + result;i--;}while (j > 0) {result = str2[j - 1] + result;j--;}return result;}
};
时间复杂度:O(n×m)
空间复杂度:O(n×m)
这道题的思路是先找到最短公共子序列LCS,然后我们知道了最短公共子序列后,就可以进而根据str1和str2还有dp进行回溯来构建出最短公共超序列result。
这道题的前面部分就是在求关于LCS的dp数组,可以参考模板力扣1143(主页有)。
这道题的难点我觉得是在回溯dp来构建result上面。
根据题目给的例子:
我们定义两个指针i和j分别指向str1和str2的最后一个元素。
当两个元素相等的时候,说明他们是LCS的一部分,所以将这个元素推入result中,由于str1和str2都包含这个元素,所以i和j都要-1。
当两个元素不相等的时候,我们就要将较不容易影响LCS的字符推入到result中,比如dp[i - 1][j] > dp[i][j - 1],也就是str[i-1]相对str[j-1]从字符串推入到result后,能尽可能保证剩下的字符串的LCS尽可能的大。
举个例子:
输入:str1 = “abac”, str2 = “cab”
在第一次判断的过程中,指针i指向str1的c,指针j指向str2的b,由于str1和str2的LCS是ab,那么b作为LCS的一部分,那么推入b就会影响到LCS(如果推入b后,那么构造LCS就没有意义,构造LCS的目的是让指针在都指向LCS的部分的时候,可以只推入一个元素,然后同时让i和j都-1)。所以我们推入c到result。
然后我们还要处理剩余部分,当某个字符串遍历完后,那么还会有一个字符串没有将元素推入到result中,这时候我们遍历完这个没遍历完的字符串,将其剩余部分推入result。
相关文章:
【动态规划-最长公共子序列(LCS)】【hard】力扣1092. 最短公共超序列
给你两个字符串 str1 和 str2,返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个,则可以返回满足条件的 任意一个 答案。 如果从字符串 t 中删除一些字符(也可能不删除),可以得到字符串 s &#x…...
图片编辑为底片,智能工具助力,创作精彩视觉作品
在当今数字化时代,图像编辑已成为表达创意和美化视觉作品的重要手段。借助智能工具,即使是初学者也能轻松驾驭图片编辑。接下为大家展示图片编辑为底片图片的效果。 1.打开“首助编辑高手”,选择这里“图片批量处理”版块页面上 2.导入保存有…...
机器学习/数据分析--用通俗语言讲解时间序列自回归(AR)模型,并用其预测天气,拟合度98%+
时间序列在回归预测的领域的重要性,不言而喻,在数学建模中使用及其频繁,但是你真的了解ARIMA、AR、MA么?ACF图你会看么?? 时间序列数据如何构造???,我打过不少…...
回溯算法之值子集和问题详细解读(附带Java代码解读)
子集和问题(Subset Sum Problem) 是一个经典的组合优化问题。问题可以这样描述: 给定一个整数集合和一个目标整数 target,我们需要从集合中选出若干个整数,使它们的和等于 target。如果这样的子集存在,返回…...
mysql游标的使用
说明: 虽然我们也可以通过筛选条件 WHERE 和 HAVING,或者是限定返回记录的关键字 LIMIT 返回一条记录,但是,却无法在结果集中像指针一样,向前定位一条记录、向后定位一条记录,或者是 随意定位到某一条记录 …...
linux udev详解
1.概念介绍 1.1sysfs文件系统 Linux 2.6以后的内核引入了sysfs文件系统,sysfs被看成是与proc、devfs和devpty同类别的文件系统,该文件系统是一个虚拟的文件系统,它可以产生一个包括所有系统硬件的层级视图,与提供进程和状态信息…...
EventSource和websocket该用哪种技术
EventSource(也称为Server-Sent Events, SSE)和WebSocket都是实现实时通信的技术,但是它们的设计目的和使用场景有所不同。在选择使用哪种技术时,需要根据具体的应用需求来决定。下面是一些关键点,可以帮助你做出选择&…...
通信工程学习:什么是三网融合
三网融合 三网融合,又称“三网合一”,是指电信网、广播电视网、互联网在高层业务应用上的深度融合。这一概念在近年来随着信息技术的快速发展而逐渐受到重视,并成为推动信息化社会建设的重要力量。以下是对三网融合的详细解释: 一…...
自定义类型结构体(上)
目录 结构体类型的声明结构体的概念结构体的声明特殊的声明结构的自引用 结构体变量的创建和初始化结构成员访问操作符 结构体类型的声明 结构体的概念 结构体是一些值的集合,这些值称为成员变量。结构的每个成员可以是不同类型的变量 举个例子:杰克的英语只考了6…...
b站-湖科大教书匠】4 网络层 - 计算机网络微课堂
【b站-湖科大教书匠】4 网络层 - 计算机网络微课堂_湖科大的计算机网络网课-CSDN博客...
国际 Android WPS Office v18.13 解锁版
WPS Office 移动版,设计不断优化,性能再次提升!融入Google Android最新设计标准,Material Design设计风格,完美支持沉浸式!简化文档操作,全新移动办公力作。全新界面更清晰舒适,功能…...
【中间件学习】Git的命令和企业级开发
一、Git命令 1.1 创建Git本地仓库 仓库是进行版本控制的一个文件目录。我们要想对文件进行版本控制,就必须创建出一个仓库出来。创建一个Git本地仓库对应的命令是 git init ,注意命令要在文件目录下执行。 hrxlavm-1lzqn7w2w6:~/gitcode$ pwd /home/hr…...
FTP连接池与多线程FTP上传下载算法(Java)
设计一个能够处理FTP连接池在多线程环境下,尤其是涉及到故障重连时避免竞争条件的算法,需要综合考虑线程同步、连接状态管理和重试机制。以下是一个设计思路和实现方案: 设计思路 连接池管理: 维护一个连接池,其中包含多个FTP连接对象。每个FTP连接对象需有状态标记(如…...
Spring Cloud微服务详解
Spring Cloud微服务详解 在当今的数字化时代,微服务架构已成为构建大型、复杂应用系统的主流方式。Spring Cloud,作为微服务领域的一颗璀璨明星,以其强大的功能和灵活的架构,吸引了无数开发者的目光。本文将深入探讨Spring Cloud…...
QT学习笔记1.2(QT的应用)
QT原生用于c的开发, 主要应用于电脑、桌面手机桌面软件的开发,主要是widget样式模板。 Qt Widgets、Qt Quick 和 Qt for Python 是 Qt 框架中的三种不同的技术,分别用于不同的应用场景。以下是它们的详细介绍和对比: 1. Qt Widg…...
数学建模算法与应用 第1章 线性规划
第1章 线性规划 线性规划是数学规划领域的重要分支,广泛应用于资源配置、生产计划、物流管理等领域。它主要用于解决如何在满足一定约束条件下,使目标函数(如成本、利润等)达到最大或最小的问题。第一章将介绍线性规划的基本概念…...
使用 systemd 设置 PHP 程序为服务
使用 systemd 设置 PHP 程序为服务 在现代 Linux 系统中,systemd 是用于管理和控制服务的标准工具。通过 systemd,我们可以轻松地将 PHP 程序配置为后台运行的系统服务,从而实现自动化启动、重启和日志记录等功能。本文将介绍如何为 PHP 程序…...
HRNET模型实现钢板表面缺陷检测
关于深度实战社区 我们是一个深度学习领域的独立工作室。团队成员有:中科大硕士、纽约大学硕士、浙江大学硕士、华东理工博士等,曾在腾讯、百度、德勤等担任算法工程师/产品经理。全网20多万粉丝,拥有2篇国家级人工智能发明专利。 社区特色…...
28 基于51单片机的两路电压检测(ADC0808)
目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机,通过ADC0808获取两路电压,通过LCD1602显示 二、硬件资源 基于KEIL5编写C代码,PROTEUS8.15进行仿真,全部资源在页尾,提供…...
SpringBootTest Mockito 虚实结合编写测试
SpringBootTest & Mockito 虚实结合测试 起因 单一使用mockito,会出现很多mock困难的问题,导致测试编写过程太长,太恶心 单一使用springboottest,会遇到需要外部接口的地方,这个时候就非得去真实调用才行。也很恶…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
