最长公共子序列

[编程题]最长公共子序列

热度指数：6644 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则输出-1。

输入描述:

输出包括两行，第一行代表字符串str1，第二行代表str2。

输出描述:

输出一行，代表他们最长公共子序列。如果公共子序列的长度为空，则输出-1。

示例1

输入

1A2C3D4B56
B1D23CA45B6A

输出

说明

"123456"和“12C4B6”都是最长公共子序列，任意输出一个。

备注:

时间复杂度，空间复杂度。(n,m分别表示两个字符串长度)

算法知识视频讲解

xxxx53

发表于 2022-05-05 17:26:06

def cal(str1: str, str2: str): ''' str1:第一个字符串 str2:第二个字符串 return:最长公共子序列 ''' &n 展开全文

秋風掃落葉

发表于 2019-09-10 11:27:31

牛客网：求两个字符串的最长公共子序列问题题目：给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。解析：用二维数组记录公共子序列长度的轨迹，根据数组逆向拼接即可。参考：https://blog.csdn.net/qq_41693034/article 展开全文

总之就是非常可爱

发表于 2022-02-14 21:05:51

//经典动态规划的题 #include<bits/stdc++.h> using namespace std; int main(){ string str1,str2; cin>>str1>>str2; & 展开全文

GoodLuck490332048

发表于 2022-10-24 16:12:40

s1 = input() s2 = input() if not s1 or not s2: print("-1") m = len(s1) n = len(s2) r 展开全文

Huster水仙

发表于 2023-02-10 21:36:44

最长公共子序列：DP 思路：s1[i]与s2[j]是否匹配，dp[i+1][j+1]:以s[i]与s[j]为末尾匹配的最长公共序列长度，由于要输出序列，所以得到公共子序列长度后，需要从后往前拼接 ①是：dp[i+1][j+1]=dp[i][j]+1;都往前一个字符，再匹配 ②否：dp[i+1][ 展开全文