给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列
数据范围：
要求：空间复杂度 )
，时间复杂度
[编程题]最长公共子序列(二)
js测试用例是错的，正确代码应该这样：
function LCS( s1 , s2 ) {
if (s1.length > s2.length) [s1, s2] = [s2, s1];
const dp = new Array(s2.length + 1).fill('');
for (let i = 1; i <= s1.length; i++) {
let pre = '';
for (let j = 1; j <= s2.length; j++) {
const tmp = dp[j];
if (s1[i - 1] === s2[j - 1]) dp[j] = pre + s2[j - 1];
else dp[j] = dp[j].length > dp[j - 1].length ? dp[j] : dp[j - 1];
pre = tmp;
}
}
const res = dp[s2.length];
return res === '' ? '-1' : res;
}
编辑于 2021-04-07 15:59:15
回复(0)
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
string ans = "";
int len1 = s1.size(), len2 = s2.size();
vector<vector<int> > dp(len1, vector<int>(len2, 0));
for(int i=0; i<len1; ++i) {
for(int j=0; j<len2; ++j) {
if(i == 0 || j == 0) dp[i][j] = s1[i] == s2[j] ? 1 : 0;
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if(s1[i] == s2[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
}
}
}
int row = len1-1;
int col = len2-1;
while(col >=0 && col >=0 ) {
if(row-1 >= 0 && col-1 >= 0 && dp[row-1][col-1] == dp[row][col]+1){
ans+=s1[row];
col--;
row--;
}else if(row-1>=0 && dp[row-1][col] == dp[row][col]){
row--;
}else if(col-1>=0 && dp[row][col-1] == dp[row][col]) {
col--;
}else { // 到达边界，退出
break;
}
}
return ans;
}
};
发表于 2020-10-20 02:29:47
回复(0)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
int n1=s1.length(),n2=s2.length();
String[][]dp=new String[n1+1][n2+1];//表示当处理到s1的第i个元素和s2的第j个元素时公共子序列的长度
for(int i=0;i<=n1;i++){
for(int j=0;j<=n2;j++){
if(i==0||j==0) dp[i][j]="";
else if(s1.charAt(i-1)==s2.charAt(j-1)){//如果相同的话
// dp[i][j]=dp[i-1][j-1]+1;
dp[i][j]=dp[i-1][j-1]+s1.charAt(i-1);
}
else {
// dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
dp[i][j]=dp[i-1][j].length()>dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];
}
}
}
if(dp[n1][n2]=="") return "-1";
return dp[n1][n2];
}
}
编辑于 2021-03-10 14:37:50
回复(10)
class Solution {
public:
string LCS(string s1, string s2) {
// write code here
string dp[s1.size()+1][s2.size()+1];
for(int i=0;i<=s1.size();i++)
dp[i][0] = "";
for(int i=0;i<=s2.size();i++)
dp[0][i] = "";
for(int i=1;i<=s1.size();i++){
for(int j=1;j<=s2.size();j++){
if(s1[i-1]==s2[j-1]) dp[i][j] = dp[i-1][j-1]+s1[i-1];
else{
dp[i][j] = dp[i-1][j].size()>dp[i][j-1].size()?dp[i-1][j]:dp[i][j-1];
}
}
}
return dp[s1.size()][s2.size()]==""?"-1":dp[s1.size()][s2.size()];
}
};
发表于 2021-01-28 18:25:58
回复(8)
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
int len1 = s1.length() + 1;
int len2 = s2.length() + 1;
string res = "";
vector<vector<int> > dp(len1, vector<int>(len2, 0));
for (int i = 1; i < len1; ++i)
for (int j = 1; j < len2; ++j)
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
int i = len1 - 1, j = len2 - 1;
while (dp[i][j]) {
if (dp[i-1][j] == dp[i][j-1] && dp[i][j] > dp[i-1][j-1]) {
res += s1[i - 1];
--i;
--j;
}
else if (dp[i - 1][j] > dp[i][j - 1]) --i;
else --j;
}
reverse(res.begin(), res.end());
return res;
}
}; 求公共子序列长度就不多说，讲讲怎么求出具体的序列。
打印题给字符串"1A2C3D4B56"， "B1D23CA45B6A"的dp数组。
for (auto i : dp) { for (auto j : i) cout << j << ' '; cout << endl; } /* 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 2 2 2 2 2 2 0 0 1 1 2 2 2 2 2 2 2 2 2 0 0 1 1 2 2 3 3 3 3 3 3 3 0 0 1 1 2 3 3 3 3 3 3 3 3 0 0 1 2 2 3 3 3 3 3 3 3 3 0 0 1 2 2 3 3 3 4 4 4 4 4 0 1 1 2 2 3 3 3 4 4 5 5 5 0 1 1 2 2 3 3 3 4 5 【5】 5 5 0 1 1 2 2 3 3 3 4 5 5 6 6 */
找找规律，若是只需要一组最长公共子序列，那就优先往横向/优先往纵向找。
根据dp数组的建立过程不难得出命中条件可以是
dp[i-1][j] == dp[i][j-1] && dp[i][j] > dp[i-1][j-1] //前者表示不是取子序列较长者，而是当前位置字符相等 //后者是为了区别有多个公共序列等长，注意分析dp数组中括起来的部分
优先纵向：
else if (dp[i - 1][j] > dp[i][j - 1]) --i;
答案是：12C4B6
优先横向：
else if (dp[i - 1][j] >= dp[i][j - 1]) --i;答案是：123456
感觉还是没讲明白，emm
编辑于 2020-09-27 14:58:26
回复(4)
class Solution: def LCS(self , s1 , s2 ): # write code here m, n = len(s1), len(s2) dp = [[''] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + s1[i - 1] else: if len(dp[i - 1][j])>len(dp[i][j - 1]): dp[i][j] =dp[i - 1][j] else: dp[i][j] =dp[i][j - 1] if dp[m][n]=='': return -1 else: return dp[m][n]
其实是通过下面的代码改过来的
class Solution(object): def longestCommonSubsequence(self, text1, text2): """ :type text1: str :type text2: str :rtype: 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] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]
发表于 2021-09-01 11:35:29
回复(0)
从dp数组中最大的数开始，往左上角找跳变点，即是需要的字符。
因为 ：
1. 观察 dp[i][j] = dp[i-1][j-1] + 1 只有在两个字符相等时右下的数会增加1；
2. 从大到小，往左上寻找跳变点才能确保是最长公共子序列的正确字符
如图：
class Solution {
public:
string LCS(string s1, string s2) {
int sz1 = s1.size();
int sz2 = s2.size();
string res;
// 动态规划获取dp矩阵
vector<vector<int>> dp(sz1 + 1, vector<int>(sz2 + 1));
for (int i = 1; i <= sz1; ++i)
for (int j = 1; j <= sz2; ++j)
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
// 取得左上角的字符
int trace = dp[sz1][sz2];
int i = sz1, j = sz2;
while (trace) {
if (dp[i-1][j] == trace) --i;
else if (dp[i][j-1] == trace) --j;
else {
res.push_back(s1[i-1]);
--trace;
--i;
--j;
}
}
// 双指针翻转字符串
int sz = res.size();
for (int k = 0; k < sz / 2; ++k) {
auto temp = res[sz - 1 - k];
res[sz - 1 - k] = res[k];
res[k] = temp;
}
return res.empty() ? "-1" : res;
}
};
发表于 2023-03-10 20:42:21
回复(0)
class Solution:
def LCS(self , s1: str, s2: str) -> str:
if s1 is None or s2 is None:
return '-1'
len1 = len(s1)
len2 = len(s2)
dp = [[''] * (len2 + 1) for i in range(len1 + 1)]
for i in range(1, len1+1):
for j in range(1, len2+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + s1[i -1]
else:
dp[i][j] = dp[i][j-1] if len(dp[i][j-1]) > len(dp[i-1][j]) else dp[i-1][j]
return dp[-1][-1] if dp[-1][-1] != '' else '-1'
发表于 2022-05-21 16:25:37
回复(0)
经典二维DP内容，不能直接用数组保存string，需要进行状态压缩，变成只有两行的数组，C++代码，参考的一位同学的实现的。
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
int m = s1.length();
int n = s2.length();
if (m == 0 || n == 0)
return "-1";
vector<vector<string>> dp(2, vector<string>(n + 1, ""));
int row = 1;
for (int i = 1; i <= m; i++)
{
row = 1 - row;
for (int j = 1; j <= n; j++)
{
if (s1[i - 1] == s2[j - 1])
dp[row][j] = dp[1- row][j - 1] + s1[i - 1];
else
{
if (dp[row][j - 1].length() >= dp[1- row][j].length())
dp[row][j] = dp[row][j - 1];
else
dp[row][j] = dp[1 - row][j];
}
}
}
return dp[row][n] == "" ? "-1" : dp[row][n];
}
};
发表于 2021-07-30 11:06:08
回复(1)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; i ++) {
for (int j = 1; j < n + 1; j ++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else if (dp[i][j - 1] > dp[i - 1][j]) {
dp[i][j] = dp[i][j - 1];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
if (dp[m][n] == 0) return "-1";
int length = dp[m][n];
StringBuffer lcs = new StringBuffer();;
while (true) {
if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
lcs.insert(0, s1.charAt(m - 1));
length -- ;
if (length <= 0) break;
m --;
n--;
} else if (dp[m - 1][n] > dp[m][n - 1]) {
m --;
} else {
n --;
}
}
return lcs.toString();
}
}
发表于 2022-08-13 10:01:57
回复(0)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
int length1 = s1.length();
int length2 = s2.length();
StringBuffer[][] dp = new StringBuffer[length1 + 1][length2 + 1];
for (int i = 0; i <= length1; i++) {
dp[i][0] = new StringBuffer();
}
for (int i = 0; i <= length2; i++) {
dp[0][i] = new StringBuffer();
}
for (int i = 1; i <= length1; i++) {
for (int j = 1; j <= length2; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = new StringBuffer(dp[i - 1][j - 1]);
dp[i][j].append(s1.charAt(i - 1));
} else {
dp[i][j] = new StringBuffer(dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1]);
}
}
if (i > 1) {
for (int j = 0; j <= length2; j++) {
dp[i - 2][j] = null; // 清除内存
}
}
}
if (dp[length1][length2].length() == 0) {
dp[length1][length2].append(-1);
}
return dp[length1][length2].toString();
}
}
发表于 2021-05-19 13:36:34
回复(0)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
int m = s1.length(), n = s2.length();
int[][] dp = new int[m][n];
StringBuilder res = new StringBuilder();
//动态规划找到最长公共子序列
for(int i = 0; i < m;i++){
for(int j = 0; j < n;j++){
if(i==0 || j==0){
dp[i][j] = 0;
}
else{
if(s1.charAt(i) == s2.charAt(j))
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
int i = m-1, j = n-1;
while(i >= 0 && j >= 0){
if(s1.charAt(i) == s2.charAt(j)){
res.append(s1.charAt(i));
i--;
j--;
}
if(i>0 && j>0 && s1.charAt(i) != s2.charAt(j)){
if(dp[i-1][j] > dp[i][j-1])
i--;
else
j--;
//dp[i-1][j] < dp[i][j-1]时,j--;
//dp[i-1][j] = dp[i][j-1]时,i--或j--,这里统一为j--;
}
//行或列到达边界
if(i==0)j--;
if(j==0)i--;
}
if(res.toString().equals("") || res==null)return "-1";
return res.reverse().toString();
}
}
发表于 2021-04-16 17:59:42
回复(0)
public static String LCS (String s1, String s2) {
int length1 = s1.length();
int length2 = s2.length();
int[][] dp = new int[length1+1][length2+1];
char[][] dp2 = new char[length1+1][length2+1];
for (int i = 1; i <= length1; i++) {
for (int j = 1; j <= length2; j++) {
if(s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1]+1;
dp2[i][j] = s1.charAt(i-1);
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
StringBuilder sb = new StringBuilder();
int a = length1;
int b = length2;
for (int i =dp[length1][length2]; i >0 ; i--) {
boolean flag = false;
for (int j = a; j >=1 ; j--) {
for (int k = b; k >=1; k--) {
if(dp[j][k]==i && dp2[j][k]!=0 ){
sb.append(dp2[j][k]);
a = j;
b = k;
flag = true;
break;
}
}
if(flag){
break;
}
}
}
return sb.reverse().toString();
}
发表于 2020-08-31 21:18:17
回复(0)
//状态压缩，动态规划
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
int m = s1.size();
int n= s2.size();
//实际只用到 要求位置的 上(dp[i-1][j]) ，左上(dp[i-1][j-1])， 左(dp[i][j-1]) 这三个值 用2行状态压缩；
//只用1行的话 前向后遍历先更新 左 会覆盖 左上 的值 。。
// 还有一个用的2行 0行1行来回滚动 绕晕了。。。 这里就 更新一行还好理解一点
vector<vector<string>>dp(2,vector<string>(n+1));
for(int i= 1;i<=m;i++)
{
for(int j= 1;j<=n;j++)
{
if(s1[i-1]==s2[j-1])
dp[1][j]=dp[0][j-1] + s1[i-1]; //只更新dp第2行 ，包括 左 的值
else
dp[1][j]=dp[0][j].size() > dp[1][j-1].size()?dp[0][j]:dp[1][j-1];
}
for(int k=0;k<=n;k++)
dp[0][k]=dp[1][k]; // 把1行的值赋值给dp的0行 来保存 上 ，左上 这两个位置
}
return dp[1][n]==""?"-1":dp[1][n];
}
};
发表于 2022-12-03 14:55:25
回复(1)
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// 时间复杂度O(MN)，空间复杂度O(MN)
vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
vector<vector<int>> path(s1.size() + 1, vector<int>(s2.size() + 1, 0));
for (int i = 1; i <= s1.size(); ++i) {
for (int j = 1; j <= s2.size(); ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
path[i][j] = 1;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
dp[i][j] = dp[i - 1][j];
path[i][j] = 2;
} else {
dp[i][j] = dp[i][j - 1];
path[i][j] = 3;
}
}
}
string res = getStr(s1, s2, s1.size(), s2.size(), path);
return res.empty() ? "-1" : res;
}
string getStr(string &s1, string &s2, int i, int j, vector<vector<int>> &path) {
string res;
if (i == 0 || j == 0) return res;
if (path[i][j] == 1) {
res += getStr(s1, s2, i - 1, j - 1, path);
res += s1[i - 1];
} else if (path[i][j] == 2) {
res += getStr(s1, s2, i - 1, j, path);
} else if (path[i][j] == 3) {
res += getStr(s1, s2, i, j - 1, path);
}
return res;
}
};
发表于 2022-11-07 17:23:31
回复(0)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
if (s1==null||s2==null||s1.length()==0||s2.length()==0){
return "-1";
}
int m=s1.length();
int n=s2.length();
//dp[a][b]，a in [0,m], b in [0,n]，定义为s1长度为a的前缀子串，s2长度为b的前缀子串，两个前缀子串的最大公共子序列
String[][]dp=new String[m+1][n+1];
for (int i=0;i<m+1; ++i){
dp[i][0] = "";
}
for (int j=0;j<n+1; ++j){
dp[0][j] = "";
}
for (int i=1; i<m+1; ++i){
for (int j=1; j<n+1; ++j){
if (s1.charAt(i-1) == s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + s1.substring(i-1,i);
}else {
dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length() ? dp[i-1][j] : dp[i][j-1];
}
}
}
String res = dp[m][n];
return res.isEmpty() ? "-1" : res;
}
}
发表于 2022-08-07 22:03:30
回复(0)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
int len1 = s1.length();
int len2 = s2.length();
String[][] dp = new String[len1+1][len2+1];
//初始化
for(int i = 0;i <= len2;i++){
dp[0][i] = "";
}
for(int i = 0; i <= len1; i++){
dp[i][0] = "";
}
for(int i = 1; i <= len1; i++){
for(int j = 1;j <= len2; j++){
if(s1.charAt(i - 1) == s2.charAt( j - 1)){
dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1);
}else{
dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length()? dp[i-1][j]: dp[i][j-1];
}
}
}
return dp[len1][len2] == "" ? "-1" : dp[len1][len2];
}
}
发表于 2022-07-30 21:49:10
回复(0)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
int l1=s1.length();
int l2=s2.length();
String[][] dp=new String[l1+1][l2+1];
for(int i=0;i<=l1;i++){
dp[i][0]="";
}
for (int i=0;i<=l2;i++){
dp[0][i]="";
}
for(int i=1;i<=l1;i++){
for (int j=1;j<=l2;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+s1.charAt(i-1);
}else {
dp[i][j]=dp[i-1][j].length()>dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];
}
}
}
return dp[l1][l2]==""?"-1":dp[l1][l2];
}
}
发表于 2022-03-27 12:07:53
回复(1)
class Solution: def LCS(self, s1, s2): l1, l2 = len(s1), len(s2) dst = [[''] * (l2 + 1) for _ in range(l1 + 1)] for i in range(1, l1 + 1): for j in range(1, l2 + 1): # 两个字符串当前位置字符相等，把当前字符加入公共子序列 if s1[i - 1] == s2[j - 1]: dst[i][j] = dst[i - 1][j - 1] + s1[i - 1] # 两字符串当前位置字符不相等，公共子序列取前面较长的一个 else: dst[i][j] = max(dst[i - 1][j], dst[i][j - 1], key=len) if not dst[l1][l2]: return -1 else: return dst[l1][l2]
发表于 2022-03-10 17:00:28
回复(0)
问题信息
难度：
179条回答
1994收藏
10539浏览
通过挑战的用户
查看代码-
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号
