首页 > 试题广场 >

最长公共子序列(二)

[编程题]最长公共子序列(二)
  • 热度指数:114556 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个字符串str1和str2,输出两个字符串的最长公共子序列。如果最长公共子序列为空,则返回"-1"。目前给出的数据,仅仅会存在一个最长的公共子序列

数据范围:
要求:空间复杂度 ,时间复杂度
示例1

输入

"1A2C3D4B56","B1D23A456A"

输出

"123456"
示例2

输入

"abc","def"

输出

"-1"
示例3

输入

"abc","abc"

输出

"abc"
示例4

输入

"ab",""

输出

"-1"
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , s1 , s2 ):
        # write code here
        start, maxlen = 0, 0
        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:
                    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'

class Solution:
    def LCS(self , s1 , s2 ):
        # write code here
        n1, n2 = len(s1), len(s2)
        dp = [[0]*(n2+1) for _ in range(n1+1)]
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        if dp[-1][-1] == 0:
            return str(-1)
        res, i, j = "", n1, n2
        while i > 0 and j > 0:
            if s1[i-1] == s2[j-1]:
                res += s1[i-1]
                i -= 1
                j -= 1
            else:
                if dp[i][j-1] >= dp[i-1][j]:
                    j -= 1
                else:
                    i -= 1
        return res[::-1]

编辑于 2021-07-26 22:26:47 回复(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;
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内容,不能直接用数组保存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)
难道没人吐槽这个题意表达不清吗?容易让人误解为连续的公共子序列
发表于 2022-08-16 18:48:20 回复(2)
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)
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) {
        // 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) {
        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)