当前位置: 首页 > news >正文

LeetCode-1143. 最长公共子序列【字符串 动态规划】

LeetCode-1143. 最长公共子序列【字符串 动态规划】

  • 题目描述:
  • 解题思路一:动规五部曲
  • 解题思路二:1维DP
  • 解题思路三:0

题目描述:

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1:

输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace” ,它的长度为 3 。
示例 2:

输入:text1 = “abc”, text2 = “abc”
输出:3
解释:最长公共子序列是 “abc” ,它的长度为 3 。
示例 3:

输入:text1 = “abc”, text2 = “def”
输出:0
解释:两个字符串没有公共子序列,返回 0 。

提示:

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

解题思路一:动规五部曲

  1. 确定dp数组(dp table)以及下标的含义
    dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

有同学会问:为什么要定义长度为[0, i - 1]的字符串text1,定义为长度为[0, i]的字符串text1不香么?

这样定义是为了后面代码实现方便,如果非要定义为长度为[0, i]的字符串text1也可以,我在 动态规划:718. 最长重复子数组 (opens new window)中的「拓展」里 详细讲解了区别所在,其实就是简化了dp数组第一行和第一列的初始化逻辑。

  1. 确定递推公式
    主要就是两大情况: text1[i - 1] 与 text2[j - 1]相同,text1[i - 1] 与 text2[j - 1]不相同

如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。

即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

  1. dp数组如何初始化
    先看看dp[i][0]应该是多少呢?

test1[0, i-1]和空串的最长公共子序列自然是0,所以dp[i][0] = 0;

同理dp[0][j]也是0。

其他下标都是随着递推公式逐步覆盖,初始为多少都可以,那么就统一初始为0。

  1. 确定遍历顺序
    从递推公式,可以看出,有三个方向可以推出dp[i][j],如图:
    在这里插入图片描述那么为了在递推的过程中,这三个方向都是经过计算的数值,所以要从前向后,从上到下来遍历这个矩阵。

  2. 举例推导dp数组
    以输入:text1 = “abcde”, text2 = “ace” 为例,dp状态如图:
    在这里插入图片描述
    最后红框dp[text1.size()][text2.size()]为最终结果

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:# 创建一个二维数组 dp,用于存储最长公共子序列的长度dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]# 遍历 text1 和 text2,填充 dp 数组for i in range(1, len(text1) + 1):for j in range(1, len(text2) + 1):if text1[i - 1] == text2[j - 1]:# 如果 text1[i-1] 和 text2[j-1] 相等,则当前位置的最长公共子序列长度为左上角位置的值加一dp[i][j] = dp[i - 1][j - 1] + 1else:# 如果 text1[i-1] 和 text2[j-1] 不相等,则当前位置的最长公共子序列长度为上方或左方的较大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])# 返回最长公共子序列的长度return dp[len(text1)][len(text2)]# 同意
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [[0] * (n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):if text1[i-1] != text2[j-1]:dp[i][j] = max(dp[i-1][j], dp[i][j-1])else:dp[i][j] = dp[i-1][j-1] + 1return dp[-1][-1]

时间复杂度:O(nm)
空间复杂度:O(nm)

解题思路二:1维DP

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [0] * (n + 1)  # 初始化一维DP数组for i in range(1, m + 1):prev = 0  # 保存上一个位置的最长公共子序列长度for j in range(1, n + 1):curr = dp[j]  # 保存当前位置的最长公共子序列长度if text1[i - 1] == text2[j - 1]:# 如果当前字符相等,则最长公共子序列长度加一dp[j] = prev + 1else:# 如果当前字符不相等,则选择保留前一个位置的最长公共子序列长度中的较大值dp[j] = max(dp[j], dp[j - 1])prev = curr  # 更新上一个位置的最长公共子序列长度return dp[n]  # 返回最后一个位置的最长公共子序列长度作为结果

时间复杂度:O(nm)
空间复杂度:O(n)

解题思路三:0


时间复杂度:O(n)
空间复杂度:O(n)

相关文章:

LeetCode-1143. 最长公共子序列【字符串 动态规划】

LeetCode-1143. 最长公共子序列【字符串 动态规划】 题目描述&#xff1a;解题思路一&#xff1a;动规五部曲解题思路二&#xff1a;1维DP解题思路三&#xff1a;0 题目描述&#xff1a; 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长 公共子序列 的长度。…...

从0开始创建单链表

前言 这次我来为大家讲解链表&#xff0c;首先我们来理解一下什么是单链表&#xff0c;我们可以将单链表想象成火车 每一节车厢装着货物和连接下一个车厢的链子&#xff0c;单链表也是如此&#xff0c;它是将一个又一个的数据封装到节点上&#xff0c;节点里不仅包含着数据&…...

STC89C52学习笔记(十)

STC89C52学习笔记&#xff08;十&#xff09; 综述&#xff1a;本文介绍了DS18B20和单总线协议&#xff0c;以及讲述了如何使用DS18B20测量温度。 一、单总线协议 1.只有一根通讯线&#xff1a;DQ &#xff08;常见的运用单总线的两种设备&#xff1a;DS18B20和DHT11&#…...

初识二叉树和二叉树的基本操作

目录 一、树 1.什么是树 2. 与树相关的概念 二、二叉树 1.什么是二叉树 2.二叉树特点 3.满二叉树与完全二叉树 4.二叉树性质 相关题目&#xff1a; 5.二叉树的存储 6.二叉树的遍历和基本操作 二叉树的遍历 二叉树的基本操作 一、树 1.什么是树 子树是不相交的;…...

如何开辟动态二维数组(C语言)

1. 开辟动态二维数组 C语言标准库中并没有可以直接开辟动态二维数组的函数&#xff0c;但我们可以通过动态一维数组来模拟动态二维数组。 二维数组其实可以看作是一个存着"DataType []"类型数据的一维数组&#xff0c;也就是存放着一维数组地址的一维数组。 所以&…...

【MATLAB第104期】基于MATLAB的xgboost的敏感性分析/特征值排序计算(针对多输入单输出回归预测模型)

【MATLAB第104期】基于MATLAB的xgboost的敏感性分析/特征值排序计算&#xff08;针对多输入单输出回归预测模型&#xff09; 因matlab的xgboost训练模型不含敏感性分析算法&#xff0c;本文通过使用single算法&#xff0c;即单特征因素对输出影响进行分析&#xff0c;得出不同…...

C语言程序与设计——工程项目开发

之前我们已经了解了C语言的基础知识部分&#xff0c;掌握这些之后&#xff0c;基本就可以开发一些小程序了。在开发时&#xff0c;就会出现合作的情况&#xff0c;C语言是如何协作开发的呢&#xff0c;将在这一篇文章进行演示。 工程项目开发 在开发过程中&#xff0c;你接到…...

【Java核心技术】第6章 接口

1 接口 接口不是类&#xff0c;而是对希望符合这个接口的类的一组需求 1.1 Comparable 接口 要对对象进行比较&#xff0c;就要实现(implement)比较(comparable)接口 注意&#xff1a; implements Comparable<Manager> Comparable接口是泛型接口 class Manager exten…...

【Java探索之旅】从输入输出到猜数字游戏

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; Java编程秘籍 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一、输入输出1.1 输出到控制台1.2 从键盘输入 二、猜数字游戏2.1 所需知识&#xff1a…...

【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II

【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II 解法 ---------------&#x1f388;&#x1f388;题目链接&#x1f388;&#x1f388;------------------- 解法 &#x1f612;: 我的代码实现> 动规五部曲 ✒️确定dp数组以及下标的含义 dp[j]表示容量为…...

2023 年上海市大学生程序设计竞赛 - 四月赛

A. 宝石划分 A. 宝石划分 - 2023 年上海市大学生程序设计竞赛 - 四月赛 - ECNU Online Judge 找距离N最近的M的因数q&#xff0c;输出M/q 如果是暴力所的话&#xff0c;会超时 #include <bits/stdc.h> using namespace std; int main(){ios::sync_with_stdio(false)…...

别让这6个UI设计雷区毁了你的APP!

一款成功的APP不仅仅取决于其功能性&#xff0c;更取决于用户体验&#xff0c;这其中&#xff0c;UI设计又至关重要。优秀的UI设计能够为用户带来直观、愉悦的交互体验&#xff0c;甚至让用户“一见钟情”&#xff0c;从而大大提高产品吸引力。 然而&#xff0c;有很多设计师在…...

继承【C/C++复习版】

目录 一、什么是继承&#xff1f;怎么定义继承&#xff1f; 二、继承关系和访问限定符&#xff1f; 三、基类和派生类对象可以赋值转换吗&#xff1f; 四、什么是隐藏&#xff1f;隐藏vs重载&#xff1f; 五、派生类的默认成员函数&#xff1f; 1&#xff09;派生类构造函…...

题目 2694: 蓝桥杯2022年第十三届决赛真题-最大数字【暴力解法】

最大数字 原题链接 &#x1f970;提交结果 思路 对于每一位&#xff0c;我我们都要尽力到达 9 所以我们去遍历每一位, 如果是 9 直接跳过这一位 如果可以上调到 9 我们将这一位上调到 9 &#xff0c;并且在a 中减去对应的次数 同样的&#xff0c;如果可以下调到 9&#xff0c;我…...

【C语言】- C语言字符串函数详解

C语言字符串函数详解 1、void *memset(void *dest, int c, size_t count); 将dest前面count个字符置为字符c. 返回dest的值. 2、void *memmove(void *dest, const void *src, size_t count); 从src复制count字节的字符到dest. 如果src和dest出现重叠, 函数会自动处理. 返回…...

如何实现小程序滑动删除组件+全选批量删除组件

如何实现小程序滑动删除组件全选批量删除组件 一、简介 如何实现小程序滑动删除组件全选批量删除组件 采用 uni-app 实现&#xff0c;可以适用微信小程序、其他各种小程序以及 APP、Web等多个平台 具体实现步骤如下&#xff1a; 下载开发者工具 HbuilderX进入 【Dcloud 插…...

基于SSM+Jsp+Mysql的农产品供销服务系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…...

​​​​网络编程学习探索系列之——广播原理剖析

hello &#xff01;大家好呀&#xff01; 欢迎大家来到我的网络编程系列之广播原理剖析&#xff0c;在这篇文章中&#xff0c; 你将会学习到如何在网络编程中利用广播来与局域网内加入某个特定广播组的主机&#xff01; 希望这篇文章能对你有所帮助&#xff0c;大家要是觉得我写…...

小程序开发SSL证书下载和安装

在开发小程序时&#xff0c;确保数据的安全传输至关重要&#xff0c;而实现这一目标的关键在于正确获取与安装SSL证书。以下详细介绍了从获取到安装SSL证书的完整流程&#xff0c;以助您为小程序构建可靠的加密通信环境。 一、小程序SSL证书类型选择&#xff1a; 域名验证型D…...

医疗图像分割 | 基于Pyramid-Vision-Transformer算法实现医疗息肉分割

项目应用场景 面向医疗图像息肉分割场景&#xff0c;项目采用 Pytorch Pyramid-Vision-Transformer 深度学习算法来实现。 项目效果 项目细节 > 具体参见项目 README.md (1) 模型架构 (2) 项目依赖&#xff0c;包括 python 3.8、pytorch 1.7.1、torchvision 0.8.2(3) 下载…...

蓝桥杯 每日2题 day5

碎碎念&#xff1a;哦哈呦&#xff0c;到第二天也是哦哈哟&#xff0c;&#xff0c;学前缀和差分学了半天&#xff01;day6堂堂连载&#xff01; 0.单词分析 14.单词分析 - 蓝桥云课 (lanqiao.cn) 关于这题就差在input前加一个sorted&#xff0c;记录一下下。接下来就是用字…...

[ 云计算 | AWS 实践 ] Java 应用中使用 Amazon S3 进行存储桶和对象操作完全指南

本文收录于【#云计算入门与实践 - AWS】专栏中&#xff0c;收录 AWS 入门与实践相关博文。 本文同步于个人公众号&#xff1a;【云计算洞察】 更多关于云计算技术内容敬请关注&#xff1a;CSDN【#云计算入门与实践 - AWS】专栏。 本系列已更新博文&#xff1a; [ 云计算 | …...

循环单链表算法库

学习贺老师数据结构 数据结构之自建算法库——循环单链表_循环单链表 csdn-CSDN博客​​​​​​ 整理总结出的循环单链表算法库 v1.0 : 基本实现功能 v2.0(2024.4.6): 修复Delete_SpecificLocate_CyclicList()删除节点函数bug,添加验证删除节点是否超范围判断 目录 1.主要功能…...

WPS二次开发系列:Gradle版本、AGP插件与Java版本的对应关系

背景 最近有体验SDK的同学反馈接入SDK出现报错&#xff0c;最终定位到原因为接入的宿主app项目的gradle版本过低导致&#xff0c;SDK兼容支持了android11的特性&#xff0c;需要对应的gradle插件为支持android11的版本。 现象 解决方案 将gradle版本升级至支持android11的插件版…...

绿联 安装MariaDB数据库用于Seatable服务

绿联 安装MariaDB数据库用于Seatable服务 MariaDB MariaDB 是一个流行的开源关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它是MySQL的一个分支&#xff0c;提供了丰富的功能和性能&#xff0c;适用于各种应用场景。 核心功能 SQL支持: MariaDB完全支持SQL&a…...

Spark, Storm, Flink简介

目录 1.Spark VS Storm2.Storm VS Flink 本文主要介绍Spark, Storm, Flink的区别。 1.Spark VS Storm Spark和Storm都是大数据处理框架&#xff0c;但它们在设计理念和使用场景上有一些区别&#xff1a; 实时性&#xff1a;Storm是一个实时计算框架&#xff0c;适合需要实时…...

【攻防世界】mfw(.git文件泄露)

首先进入题目环境&#xff0c;检查页面、页面源代码、以及URL&#xff1a; 发现页面无异常。 使用 dirsearch 扫描网站&#xff0c;检查是否存在可访问的文件或者文件泄露&#xff1a; 发现 可访问界面/templates/ 以及 .git文件泄露&#xff0c;故使用 GItHack 来查看泄露的 …...

递归神经网络(Recursive Neural Networks)

递归神经网络&#xff08;Recursive Neural Networks&#xff09;是一种特殊的神经网络&#xff0c;它们通过处理具有树形结构的数据来捕获数据的深层次关系&#xff0c;尤其是在自然语言处理和计算机视觉中的一些应用&#xff0c;如语法分析和场景理解。 1. 理解基本概念和背…...

【leetcode面试经典150题】29.三数之和(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…...

ThinkPHP审计(1) 不安全的SQL注入PHP反序列化链子phar利用简单的CMS审计实例

ThinkPHP代码审计(1) 不安全的SQL注入&PHP反序列化链子phar利用&简单的CMS审计实例 文章目录 ThinkPHP代码审计(1) 不安全的SQL注入&PHP反序列化链子phar利用&简单的CMS审计实例一.Thinkphp5不安全的SQL写法二.Thinkphp3 SQL注入三.Thinkphp链5.1.x结合phar实现…...