给定两个字符串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)
动态规划，考虑到边界条件，令dp[i][j]表示截止s1第i-1位，s2第j-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 - 1][j].size() > dp[i][j - 1].size() ? dp[i - 1][j] : dp[i][j - 1]; //取较长的那个。
}
string LCS(string s1, string s2) {
int n1 = s1.length();
int n2 = s2.length();
if (n1 == 0 || n2 == 0) {
return "-1";
}
// dp[i][j]表示s1第i-1位，s2第j-1位的最长公共序列
vector<vector<string>> dp(n1 + 1, vector<string>(n2 + 1, ""));
//动态规划
for (int i = 1; i <= n1; ++i) {
for (int j = 1; j <= n2; ++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[n1][n2] == "" ? "-1" : dp[n1][n2];
}
可惜不能AC，当数据长度较长时，空间复杂度会爆掉。因此必须想办法压缩空间。一种办法是参考官方解题思路，使用首尾下标来代替字符串。不过仔细观察dp这个二维数组，其实不难发现，每次计算只用到了i和i-1，也就是外面那层循环完全可以用临时变量来代替。那么简化后就只需要用一维数组，大大节省了空间。
代码如下：
代码如下：
string LCS(string s1, string s2) {
int n1 = s1.length();
int n2 = s2.length();
if (n1 == 0 || n2 == 0) {
return "-1";
}
vector<string> dp(n2 + 1, "");
for (int i = 1; i <= n1; ++i) {
string str = "";
for (int j = 1; j <= n2; ++j) {
string tmp = dp[j];
if (s1[i - 1] == s2[j - 1]) {
dp[j] = str + s2[j - 1];
} else if (dp[j - 1].size() > dp[j].size()) {
dp[j] = dp[j - 1];
}
str = tmp;
}
}
return dp[n2] == "" ? "-1" : dp[n2];
}
发表于 2024-12-10 09:48:42
回复(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)
public class Solution {
public String LCS (String s1, String s2) {
// 字符串1的长度
int sLen1 = s1.length();
// 字符串2的长度
int sLen2 = s2.length();
// dp数组，初始化高度和宽度分别为两个字符串长度+1
// 目的是方便初始化，如果高度和宽度分别是两个字符串的长度，初始化会比较麻烦
// s1[0,i)和s2[0,j)所构成的最长子序列是dp[i][j]
String[][] dp = new String[sLen1 + 1][sLen2 + 1];
// dp数组初始化
for (int i = 0; i <= sLen1; i++) {
dp[i][0] = "";
}
for (int j = 0; j <= sLen2; j++) {
dp[0][j] = "";
}
// 遍历每一种情况
for (int i = 1; i <= sLen1; i++) {
for (int j = 1; j <= sLen2; j++) {
// 因为长度和宽度都是字符串长度+1，所以这里取字符的时候需要减1，保证不越界
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// 因为要加入的两个字符一样，所以直接取两个字符加入前的最长公共子序列然后加上这个相等的字符
dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
} else {
// 取s1不加入当前字符和s2不加入当前字符的情况中的最长的那个子序列
if (dp[i - 1][j].length() >= dp[i][j - 1].length()) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
}
return "".equals(dp[sLen1][sLen2]) ? "-1" : dp[sLen1][sLen2];
}
}
发表于 2023-05-31 09:26:21
回复(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)
问题信息
难度：
192条回答
2243收藏
12390浏览
通过挑战的用户
查看代码-
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号
