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] + 1
                else:
                    # 如果 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] + 1
        return 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 + 1
                else:
                    # 如果当前字符不相等,则选择保留前一个位置的最长公共子序列长度中的较大值
                    dp[j] = max(dp[j], dp[j - 1])
                prev = curr  # 更新上一个位置的最长公共子序列长度
        
        return dp[n]  # 返回最后一个位置的最长公共子序列长度作为结果

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

解题思路三:0


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

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

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

相关文章

TSINGSEE青犀AI智能分析网关V4吸烟/抽烟检测算法介绍及应用

抽烟检测AI算法是一种基于计算机视觉和深度学习技术的先进工具&#xff0c;旨在准确识别并监测个体是否抽烟。该算法通过训练大量图像数据&#xff0c;使模型能够识别出抽烟行为的关键特征&#xff0c;如烟雾、手部动作和口部形态等。 在原理上&#xff0c;抽烟检测AI算法主要…

【目标检测数据集】城市街道垃圾堆相关数据集

一、GarbageOverflow&#xff1a;城市街道垃圾堆数据集 该垃圾堆数据集是通过爬虫从网上进行爬取得到的&#xff0c;一共包含1188张图片&#xff0c;有2个类别&#xff0c;分别为[overflow, No Overflow]&#xff0c;两个标签的数量分别为1734个标签和414个标签。部分数据集及…

中国历年GDP统计-探数API统计

数据介绍 时间维度&#xff1a;1978年-2021年 单位&#xff1a;亿元 该数据来源于国家统计局发布的中国统计年鉴2021&#xff0c;为按当年价格计算的中国历年GDP以及人均GDP。 数据说明&#xff1a; 数据来源于国家统计局。

【更新】全国省级-新质生产力数据集(2010-2022年)

01、数据简介 新质生产力&#xff0c;又称为新型生产力&#xff0c;是指在现代科技和经济社会发展的推动下&#xff0c;由新的生产要素、生产方式、生产关系等构成的具有新质特点的生产力。这种生产力突破了传统生产力的局限&#xff0c;具有更高的效率和创造力&#xff0c;是…

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

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

黄金基金和黄金有什么区别?

黄金基金本质上是一种投资工具&#xff0c;它通过间接投资黄金或与其紧密相关的金融衍生品来反映黄金市场的表现。不同于直接持有实物黄金&#xff0c;投资者购买黄金基金并不涉及实体黄金的保管问题&#xff0c;而是将资金交由专业的基金管理人管理&#xff0c;由他们代表投资…

Input DropDown 拼接成 select组件(基于antd和react)

前言&#xff1a;为什么不直接用select&#xff0c;还要舍近求远搞inputdropdown这种缝合怪&#xff0c;是因为antd的select不支持选中项再编辑&#xff0c;效果如图 比如&#xff1a;选中的lucy文案变成了placeholder不能再编辑了 封装此组件虽然比较简单&#xff0c;但还是有…

一文读懂Partisia Blockchain,被严重低估的隐私区块链生态

在今年 3 月&#xff0c;隐私公链 Partisia Blockchain 迎来了重要的进展&#xff0c;该生态通证 $MPC 上线了交易所&#xff0c;目前 $MPC 通证可以在 Kucoin、Gate、BitMart、Bitfinex、Bitture 等平台交易&#xff0c;并将在不久后上线 MEXC 平台。 在上个月上线市场至今&am…

中颖51芯片学习4. 可编程计数器阵列PCA0

中颖51芯片学习4. 可编程计数器阵列PCA0 一、PCA介绍1. PCA简介2. SH79F9476的PCA0特性3. PCA0 功能4. 时钟5. PCA0原理框图6. 工作方式 二、PCA0寄存器1. PCA0标志寄存器2. PCA使能寄存器3. PCA0方式寄存器4. P0CPMn PCA捕捉/比较寄存器5. P0FORCE强制输出控制寄存器6. PCA0计…

期货量化交易软件:MQL5 中的范畴论 (第 15 部分)函子与图论

概述 在上一篇文章中&#xff0c;我们目睹了前期文章中涵盖的概念&#xff08;如线性序&#xff09;如何视作范畴&#xff0c;以及为什么它们的“态射”在与其它范畴相关时即构成函子。在本文中&#xff0c;我们赫兹量化软件将阐述来自前期文章中的概括&#xff0c;即通过查看…

三方库移植之NAPI开发[2]C/C++与JS的数据类型转

通过NAPI框架进行C/C与JS数据类型的转换 OpenHarmony NAPI将ECMAScript标准中定义的Boolean、Null、Undefined、Number、BigInt、String、Symbol和Object八种数据类型&#xff0c;以及函数对应的Function类型&#xff0c;统一封装成napi_value类型&#xff0c;下文中表述为JS类…

基于LNMP部署wordpress

目录 一.环境准备 二.配置源并安装 三.配置Nginx 四.配置数据库 五.上传源码并替换 六.打开浏览器&#xff0c;输入虚拟机ip访问安装部署 七.扩展增加主题 一.环境准备 centos7虚拟机 关闭防火墙和seliunx stop firewalld #关闭防火墙 setenforce 0 …

隐身打击云函数CDN对抗 | 应急响应

0x00 简介 在攻防演练中&#xff0c;使用云函数来隐藏 C&C 的 ip 地址已经成为了一种“标配” 在应急处置过程中&#xff0c;我们经常遇到 netstat -pantu | grep ip 无法找到安全设备关于红队外联的告警的情况 由于 C&C 的 ip 地址是一直变化的&#xff0c;所以常…

基于深度学习的智能停车场车牌识别计费系统(完整程序+训练数据集+开题报告+论文))

摘要 本篇论文研究的是基于车牌识别技术的智能停车场管理系统&#xff0c;采用基于深度学习的车牌识别算法&#xff0c;通过卷积神经网络对车牌图像进行处理和分析&#xff0c;实现车牌字符的识别和车牌信息的提取。同时&#xff0c;本文还设计了一个智能停车场管理系统…

【网安播报】GitHub上的恶意Visual Studio 项目推送 Keyzetsu 恶意软件

1、GitHub 上的恶意 Visual Studio 项目推送 Keyzetsu 恶意软件 威胁行为者正在滥用 GitHub 自动化功能和恶意 Visual Studio 项目来推送“Keyzetsu”恶意软件的新变种并窃取加密货币付款。攻击者创建了GitHub 存储库&#xff0c;并使用各种方法来人为地提高其在平台上的受欢迎…

计费管理系统

武汉理工大学程序设计综合实验作业&#xff0c;没有完全按照要求的文件来写&#xff0c;仅供参考。 目录 菜单说明 大致思路说明 代码实现 func.h 用于存放各种功能函数的声明 tool.h 用于存放相关工具函数的声明 func.c 用于存放各种功能函数的定义 tool.c 用于存放相…

网站如果在日益变化的网络攻击中寻到一线生机

一、引言 在数字化浪潮席卷全球的今天&#xff0c;网络空间早已成为国家安全、经济发展和社会稳定的战略高地。然而&#xff0c;这片看似平静的虚拟世界&#xff0c;实则暗流涌动&#xff0c;网络攻击层出不穷&#xff0c;手段日益翻新&#xff0c;给网站的安全运营带来了前所…

蓝桥杯2022年第十三届省赛真题-最优清零方案 java

样例输入、输出&#xff1a; 输入1&#xff1a; 4 2 1 2 3 4输出1 6输入2&#xff1a; 4 2 1 2 3 4输出2 6解法&#xff1a; 滑动窗口解法如下。主要思路就是&#xff1a;用长度为k的滑动窗口&#xff0c;每遇到连续k个不为0的数&#xff0c;记录这k个数中的最小值为min&…

Nerf-Studio复现笔记

文章目录 1. Env2. Train3. Custom data3.1 Prepare3.2 Render and eval3.3 Results 4. Summary 1. Env The configuration process was smooth on Linux, but there are some problems with tiny_cuda_nn and colmap in Windows. // According to the installation document…

【MATLAB源码-第186期】matlab基于MLE算法的8天线阵列DOA估计仿真,对比粗估计、精确估计输出RMSE对比图。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 第一部分&#xff1a;基本概念与系统设置 方向到达估计&#xff08;Direction of Arrival, DOA&#xff09;是信号处理中一项重要的技术&#xff0c;主要用于确定信号的到达方向。这种技术在雷达、无线通信和声纳等领域中有…