给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列
数据范围：
要求：空间复杂度 )
，时间复杂度
[编程题]最长公共子序列(二)
精华题解
题目主要信息：
找到两个字符串的最长公共子序列，子序列不要求位置在原串中连续
仅存在一个最长公共子序列，不需要去重
最长公共子序列为空需要返回"-1"，而不是空序列，最后要变换
举一反三：
学习完本题的思路你可以解决如下题目：
BM66.最长公共子串
BM71.最长上升子序列(一)
BM73 最
展开全文
class Solution {
public:
string LCS(string s1, string s2) {
if(s1.empty() || s2.empty()) return "-1";
int dp[s1.size()+1][s2.size(
展开全文
详细博客讲解 https://blog.csdn.net/hrn1216/article/details/51534607 import java.util.*;
public class Solution {
/**
* longest common subsequence
展开全文
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字
展开全文
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字
展开全文
参考的链接：https://blog.csdn.net/hrn1216/article/details/51534607 // LCS（longest common sequence（还有另一种LCS,longest common string，中文名为最长公共子串，
// 他和seque
展开全文
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
def LCS(sel
展开全文
最长公共子序列(二)（动态规划）
题意
给定两个字符串,求它们的最长公共序列
思路分析
公共序列
要找s1和s2的公共序列,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的公共序列加上相等的字符,就能得到一个更长的公共序列, 所以有, 令s[i][j]表示
展开全文
描述
题目描述
给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列
要求：空间复杂度 O(n^2) ，时间复杂度 O(n^2)
示例
输入：
"1A2C3D4B56","B1D23A456A"
返回
展开全文
题意整理 本题题意既找到给定的两个字符串中的最长公共子序列，子序列为一个序列去除部分（也可以不去除）元素后，其他元素相对位置保持不变得到的序列。 方法一：动态规划 核心思想： 分析题意可以知道可以通过二维动态规划解决这道题假设两个字符串的长度分别为 。建立一个大小为行，列的dp数组，其中表示 长度
展开全文
动态规划可以求出最长公共子序列的长度，dp[i][j]表示以i-1结尾的s1和以j-1结尾的s2之间的最长公共子序列长度，由dp[i-1][j]、dp[i][j-1]以及dp[i-1][j-1]这三个上一状态推导出当前状态。
难点在于如何根据dp表的信息得到具体的子序列。从dp的右下角到左上角方向遍
展开全文
问题信息
难度：
180条回答
1994收藏
10551浏览
通过挑战的用户
查看代码-
2023-02-21 14:40:59 -
2023-01-05 22:57:07
-
2023-01-05 10:24:08 -
2022-11-11 00:24:25
-
2022-11-10 22:31:05
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
