最长公共子序列(LeetCode-1143)

简介: 最长公共子序列(LeetCode-1143)

最长公共子序列(LeetCode-1143)


题目

给定两个字符串 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 仅由小写英文字符组成。


思路

五部曲


dp[i][j] 含义


长度为 [ 0 , i − 1 ] 的字符串text1与长度为 [ 0 , j − 1 ] 的字符串text2的最长公共子序列长度

递推公式


如果 t e x t 1 [ i − 1 ] = t e x t 2 [ j − 1 ]

d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ]


如果二者不相等

d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] )


数组初始化


dp[i][0] 与空串一起求最长公共子序列,自然为零

dp[0][j] 同理等于零

遍历顺序


从前往后

测试用例



代码展示

class Solution
{
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        int n1 = text1.size();
        int n2 = text2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; j++)
            {
                if (text1[i - 1] == text2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[n1][n2];
    }
};
目录
相关文章
|
SQL 关系型数据库 MySQL
总结 vue3 的一些知识点:MySQL LIKE 子句
总结 vue3 的一些知识点:MySQL LIKE 子句
|
SQL 安全 测试技术
【数据守护者必备】SQL数据备份与恢复策略全解析:从全量到日志备份,手把手教你确保企业信息万无一失的实战技巧!
【8月更文挑战第31天】数据库是企业核心业务数据的基石,为防止硬件故障、软件错误或人为失误导致的数据丢失,制定可靠的备份与恢复策略至关重要。本文通过一个在线购物平台的案例,详细介绍了使用 SQL Server 进行全量备份、差异备份及事务日志备份的方法,并演示了如何利用 SQL Server Agent 实现自动化备份任务。此外,还提供了数据恢复的具体步骤和测试建议,确保数据安全与业务连续性。
488 0
|
API
Vue3中的ref和shallowRef、reactive和shallowReactive
Vue3中的ref和shallowRef、reactive和shallowReactive
394 1
|
运维 监控 前端开发
[SpringAop + Logback +MDC] 现网必备全链路日志追踪
[SpringAop + Logback +MDC] 现网必备全链路日志追踪
1685 1
|
JavaScript Java 测试技术
基于SpringBoot+Vue+uniapp的家政项目的详细设计和实现(源码+lw+部署文档+讲解等)
基于SpringBoot+Vue+uniapp的家政项目的详细设计和实现(源码+lw+部署文档+讲解等)
|
存储 NoSQL 数据库
PythonIP代理池的建立和使用
PythonIP代理池的建立和使用
179 0
|
前端开发
【前端学习】—let const var之间的区别(十三)
【前端学习】—let const var之间的区别(十三)
|
JSON 监控 Dubbo
基于SkyWalking的分布式跟踪系统 - 异常告警
基于SkyWalking的分布式跟踪系统 - 异常告警
442 0
|
存储
.NET Core - 内存配置和命令行配置方式详解
.NET Core - 内存配置和命令行配置方式详解
|
存储 编译器 C语言
C++学习:从基础到QT实现
C++学习:从基础到QT实现