最长公共子序列(二)

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.length() == 0 || s2.length() == 0) {
            return "-1";
        }

        int len1 = s1.length();
        int len2 = s2.length();
        // dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        // 初始化-1
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        // 子序列的拼接方式 - 1表示来自左上（i-1, j-1）、2表示来自左（i-1, j）、3表示来自上（i, j-1）
        int[][] from = new int[len1 + 1][len2 + 1];

        // 首先获取最长子序列的最大长度，并填写from表格（用于得到子序列）
        int length = process1(s1, s2, len1, len2, dp, from);

        // 根据from表格，获取答案字符串
        String res = process2(s1, s2, len1, len2, from);

        // 检查答案是否位空
        if (res.isEmpty()) {
            return "-1";
        } else {
            return res;
        }
    }

    // 记忆化搜索
    // 获取最长公共子序列长度并填写from表
    public int process1 (String s1, String s2, int i, int j, int[][] dp,
                         int[][] from) {
        // 递归出口
        if (i == 0 || j == 0) {
            dp[i][j] = 0;
            return dp[i][j];
        }

        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        // 递归分支
        // 遇到两个字符相等，则无论[i-1][j-1]的最长公共子序列是什么情况，该字符都会令其长度+1
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            // 情况等同于dp[i-1][j-1] + 1（加上该公共字符）
            if (dp[i - 1][j - 1] == -1) {
                dp[i - 1][j - 1] = process1(s1, s2, i - 1, j - 1, dp, from);
            }
            dp[i][j] = dp[i - 1][j - 1] + 1;
            // 来自左上方
            from[i][j] = 1;
        } else {
            // 遇到的两个字符不同，则该字符必然不会进入公共子序列
            // [i][j]的情况就是[i-1][j-1]、[i][j-1]和[i-1][j]中的最大值
            // 易证，[i-1][j-1]的情况一定不会大于后面两种，因此只比较[i][j-1]和[i-1][j]即可
            // 左边的选择更大，即第一个字符串后退一位
            if (dp[i - 1][j] == -1) {
                dp[i - 1][j] = process1(s1, s2, i - 1, j, dp, from);
            }
            if (dp[i][j - 1] == -1) {
                dp[i][j - 1] = process1(s1, s2, i, j - 1, dp, from);
            }
            if (dp[i - 1][j] > dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j];
                //来自于左方
                from[i][j] = 2;
            }
            // 右边的选择更大，即第二个字符串后退一位
            else {
                dp[i][j] = dp[i][j - 1];
                // 来自于上方
                from[i][j] = 3;
            }
        }
        return dp[i][j];
    }

    // 递归获取最长公共子序列
    public String process2 (String s1, String s2, int i, int j, int[][] from) {
        String res = "";
        // 递归出口
        if (i == 0 || j == 0) {
            return "";
        }
        
        // 根据方向，往前递归，然后添加本级字符
        if (from[i][j] == 1) {
            res = process2(s1, s2, i - 1, j - 1, from) + s1.charAt(i - 1);
        } else if (from[i][j] == 2) {
            res = process2(s1, s2, i - 1, j, from);
        } else if (from[i][j] == 3) {
            res = process2(s1, s2, i, j - 1, from);
        }
        return res;
    }
}

    public String LCS (String s1, String s2) {
       
        s1=" "+s1;
        s2=" "+s2;

        int len1=s1.length();
        int len2=s2.length();

        String[][] dp=new String[len1][len2];

        //初始化""
        for(int i=0;i<len1;i++){
            dp[i][0]="";
        } 
        for(int i=0;i<len2;i++){
            dp[0][i]="";
        }

        //填充dp表
        for(int i=1;i<len1;i++){
            for(int j=1;j<len2;j++){
                if(s1.charAt(i) == s2.charAt(j)){
                    dp[i][j]=dp[i-1][j-1]+s1.charAt(i);
                }else{
                    dp[i][j]=dp[i-1][j].length()>dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];
                }
            }
        }

     
       if(dp[len1-1][len2-1]==null||dp[len1-1][len2-1]==""){
        return "-1";
       }
       return  dp[len1-1][len2-1];
    }



算法讲解：https://blog.csdn.net/weixin_71246590/article/details/141336952

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
        if (s1.equals(s2)) {
            return s1;
        }
        if (s1.equals("") || s2.equals("")) {
            return "-1";
        }

        String [][]result = new String[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i < s1.length(); i++) {
            StringBuilder string = new StringBuilder("");
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    if (i == 0 || j == 0) {

                        string.append(s1.charAt(i));
                        result[i][j] = string.toString();

                    } else {

                        result[i][j] = result[i - 1][j - 1] + s1.charAt(i);

                    }
                } else {
                    if (i == 0 || j == 0) {


                        if (i == 0 && j == 0) {
                            result[i][j] = "";
                        } else if (i == 0) {
                            result[i][j] = result[i][j - 1];
                        } else if (j == 0) {
                            result[i][j] = result[i - 1][j];
                        }

                    } else {

                        if (result[i - 1][j].length() > result[i][j - 1].length()) {
                            result[i][j] = result[i - 1][j];
                        } else {
                            result[i][j] = result[i][j - 1];
                        }

                    }
                }
            }
        }
        if (result[s1.length() - 1][s2.length() - 1].equals("")) {
            return "-1";
        } else {
            return result[s1.length() - 1][s2.length() - 1];
        }
    }
}

public String LCS (String s1, String s2) {
    // write code here
    int l1=s1.length() ,l2=s2.length();
    String[][] dp=new String[l1+1][l2+1];
    for(int i=0;i<=l1;i++){
        for(int j=0;j<=l2;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]+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].equals("")?"-1":dp[l1][l2];
}

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 n = s1.length(), m = s2.length();
        s1 = " " + s1;
        s2 = " " + s2;
        int index = 0;
        int[][] f = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if(s1.charAt(i) == s2.charAt(j)) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                    index = i;
                }
            }
        }
        if(f[n][m] == 0) return "-1";
        StringBuilder res = new StringBuilder();
        while(n > 0 && m > 0) {
            if(s1.charAt(n) == s2.charAt(m)) {
                res.append(s1.charAt(n));
                n--;
                m--;
            } else {
                if(f[n - 1][m] > f[n][m - 1]) {
                    n--;
                } else m--;
            }
        }
        return res.reverse().toString();
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
     int[][] memo;
    public String LCS (String s1, String s2) {
        // write code here
        int m = s1.length();
        int n = s2.length();
        memo = new int[m+1][n+1];
        //务必设-1，简化比较操作。
        for(int[] row : memo){
            Arrays.fill(row, -1);
        }
        dp(s1, m, s2, n);
        StringBuilder sb = new StringBuilder();
        return search(s1, s2, sb);
    }
    public String search(String s1, String s2, StringBuilder sb){
        int m = s1.length();
        int n = s2.length();

        while(m>0 && n>0){
            if(s1.charAt(m-1) == s2.charAt(n-1)){
                sb.append(s1.charAt(m-1));
                m--;
                n--;
            }else{
                //注意memo中[0][0...n]和[0...m][n]都是-1，下面判断可防止下标越界。因为-1比memo中任何有效的数字都小。所有就会m或n不断减减，直到s1.charAt(m-1) == s2.charAt(n-1)。
                if(memo[m-1][n] > memo[m][n-1]){
                    m--;
                }else{
                    n--;
                }
            }

        }
        return sb.length() == 0 ? "-1" : sb.reverse().toString();
    }
    public int dp(String s1, int i, String s2, int j){
        if(i<=0 || j<=0){
            return 0;
        }
        if(memo[i][j] != -1){
            return memo[i][j];
        }
        if(s1.charAt(i-1) == s2.charAt(j-1)){
            memo[i][j] = dp(s1, i-1, s2, j-1)+1;
        }else{
            memo[i][j] = Math.max(dp(s1,i-1,s2,j), dp(s1,i,s2,j-1));
        }
        return memo[i][j];
    }
}

public String LCS (String s1, String s2) {
        int m=s1.length();
        int 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{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        if(dp[m][n]==0) return "-1";
        StringBuilder ans=new StringBuilder();
        int len=dp[m][n];
        while(true){
            if(s1.charAt(m-1)==s2.charAt(n-1)){   //s1.length()-1、s2.length()-2
                len--;
                ans.insert(0,s1.charAt(m-1));     //sb.insert(插入的位置，插入的字符)
                if(len<=0) break;
                m--;
                n--;
            }else if(dp[m-1][n]>dp[m][n-1]){
                m--;
            }else{
                n--;
            }
        }
        return ans.toString();
    }

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];
    }
}

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
        if (s1 == null || s1.length() == 0) {
            return "-1";
        }

        if (s2 == null || s2.length() == 0) {
            return "-1";
        }

        // dp[i][j]以s1中前i个字符和s2中前j个字符的最长公共子序列
        String[][] path = new String[s1.length()][s2.length()];
        path[0][0] = s1.charAt(0) == s2.charAt(0) ? s1.charAt(0) + "" : "";

        // 第一行
        for (int i = 1; i < s2.length(); i++) {
            if (s2.charAt(i) == s1.charAt(0)) {
                path[0][i] = s1.charAt(0) + "";
            } else {
                path[0][i] = path[0][i - 1];
            }
        }

        // 第一列
        for (int i = 1; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(0)) {
                path[i][0] = s2.charAt(0) + "";
            } else {
                path[i][0] = path[i - 1][0];
            }
        }


        for (int i = 1; i < s1.length(); i++) {
            for (int j = 1; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {

                    path[i][j] = path[i - 1][j - 1] + s1.charAt(i);
                } else {

                    if (path[i][j - 1].length() > path[i - 1][j].length()) {
                        path[i][j] = path[i][j - 1];
                    } else {
                        path[i][j] = path[i - 1][j];
                    }
                }

            }
        }

        return path[s1.length() - 1][s2.length() - 1].length() > 0 ? path[s1.length() -
                1][s2.length() - 1] : "-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();
    }
}

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;
    }
}

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];
    }
}