最长公共子序列问题--动态递推求解

牛客网：求两个字符串的最长公共子序列问题
题目：给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。
解析：用二维数组记录公共子序列长度的轨迹，根据数组逆向拼接即可。
参考：https://blog.csdn.net/qq_41693034/article/details/99861347
https://blog.csdn.net/qq_21905401/article/details/52169733

import java.util.*;

public class Main {

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

public static String maxCommonStr(String str1, String str2) {
    if (str1 == null || str2 == null) {
        return "-1";
    }
    int len1 = str1.length();
    int len2 = str2.length();
    int[][] dp = new int[len1 + 1][len2 + 1];// 二维数组记录最大子序列长度
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i][j - 1] > dp[i - 1][j] ? dp[i][j - 1]
                        : dp[i - 1][j];
            }
        }
    }
    // 逆向拼接最长子序列,因为二维dp已经记录最大公共子序列的增长路径
            // 从str1和str2的末尾开始，循着dp数组的轨迹拼接即可
    StringBuffer sb = new StringBuffer();
    int index = 0;
    int i = len1, j = len2;
    while (index < dp[len1][len2]) {
        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
            sb.append(str1.charAt(i - 1));
            i--;
            j--;
            index++;
        } else {
            if (dp[i][j - 1] > dp[i - 1][j]) {
                j--;
            } else {
                i--;
            }
        }
    }
    return sb.reverse().toString();
}

}