题解 | #最长公共子序列#

import java.util.*;
public class Main {
    public static void main(String[] args){
        //样本对应模型
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        if(str1 == null|| str2 == null || str1.length() == 0|| str2.length() == 0){
            System.out.print(-1);
            return;
        }
//         System.out.print(maxCommon(str1, str2, str1.length()-1, str2.length()-1));
        int M = str1.length() + 1;
        int N = str2.length() + 1;
        String[][] dp = new String[M][N];
        for(int i = 0; i < M; i++){
            dp[i][0] = "";
        }
        for(int i = 0; i < N; i++){
            dp[0][i] = "";
        }
        //全体向右下平移一个格子
        for(int i = 1; i < M; i++){
            for(int j = 1; j < N; j++){
                if(str1.charAt(i-1) == str2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + str2.charAt(j-1);
                else{
                    String result1 = dp[i - 1][j];
                    String result2 = dp[i][j - 1];
                    //null没有分配空间，""分配了空间，因此str1还不是一个实例化的对象，而str2已经实例化。
                    if(result1.length() >= result2.length()) dp[i][j] = result1;
                    else dp[i][j] = result2;
                }
            }
        }
        if(dp[M-1][N-1] != "") System.out.print(dp[M-1][N-1]);
        else System.out.print(-1);
        
    }
    // 输入：相同字符后边的串
    // 输出：最长公共子序列
    public static String maxCommon(String str1, String str2, int p1, int p2){
        if(p1 == -1 || p2 == -1) return "";
        if(str1.charAt(p1) == str2.charAt(p2)) return maxCommon(str1, str2, p1-1, p2-1) + str1.charAt(p1);
        else{
            String result1 = maxCommon(str1, str2, p1-1, p2);
            String result2 = maxCommon(str1, str2, p1, p2-1);
            if(result1.length() >= result2.length()) return result1;
            else return result2;
        }
    }
}