最长公共子序列

import java.io.*;

public class Main{
    public static void main(String[] args)throws Exception{
        try(BufferedReader bf = new BufferedReader(new InputStreamReader(System.in))){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        String result = lcse(str1, str2);
         System.out.println(result.equals("") ? -1 : result);
        }catch(IOException e){
            e.printStackTrace();
        }
    }
     public static int[][] getdp(char[] str1,char[] str2){
        int[][] dp=new int[str1.length][str2.length];
        dp[0][0]=str1[0]==str2[0]?1:0;
        for(int i=1;i<str1.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],str1[i]==str2[0]?1:0);
        }
        for(int j=1;j<str2.length;j++){
            dp[0][j]=Math.max(dp[0][j-1],str1[0]==str2[j]?1:0);
        }
        for(int i=1;i<str1.length;i++){
            for(int j=1;j<str2.length;j++){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                if(str1[i]==str2[j]){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
        return dp;
    }
    public static String lcse(String str1,String str2){
        if(str1==null||str2==null||str1.equals("")||str2.equals("")){
            return "";
        }
        char[] chs1=str1.toCharArray();
        char[] chs2=str2.toCharArray();
        int[][] dp=getdp(chs1,chs2);
        int m=chs1.length-1;
        int n=chs2.length-1;
        char[] res=new char[dp[m][n]];
        int index=res.length-1;
        while (index>=0){
            if(n>0&&dp[m][n]==dp[m][n-1]){
                n--;
            }else if(m>0&&dp[m][n]==dp[m-1][n]){
                m--;
            }else{
                res[index--]=chs1[m];
                m--;
                n--;
            }
        }
        return String.valueOf(res);
    }
   
}

动态规划

import java.util.Scanner;

public class Main {

    public static String process(String str1, String str2) {
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
            return "";
        }
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        int[][] dp = dp(char1, char2);
        int m = str1.length() - 1;
        int n = str2.length() - 1;
        char[] res = new char[dp[m][n]];
        int index = res.length - 1;

        while (index >= 0) {
            if (n > 0 && dp[m][n] == dp[m][n - 1]) {
                n--;
            } else if (m > 0 && dp[m][n] == dp[m - 1][n]) {
                m--;
            } else {
                res[index--] = char1[m];
                m--;
                n--;
            }
        }

        return String.valueOf(res);
    }

    public static int[][] dp(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;

        for (int i = 1; i < str1.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
        }
        for (int i = 1; i < str2.length; i++) {
            dp[0][i] = Math.max(dp[0][i - 1], str2[i] == str1[0] ? 1 : 0);
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                int max = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (str1[i] == str2[j]) {
                    max = Math.max(dp[i - 1][j - 1] + 1, max);
                }
                dp[i][j] = max;
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        System.out.println(process(str1, str2));
    }
}