后端开发刷题 | 最长公共子序列（非连续）
描述
给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列。
数据范围：0≤∣str1∣,∣str2∣≤2000
要求：空间复杂度 O(n2)，时间复杂度 O(n2)
示例1
输入：
"1A2C3D4B56","B1D23A456A"
返回值：
"123456"
示例2
输入：
"abc","def"
返回值：
"-1"
示例3
输入：
"abc","abc"
返回值：
"abc"
示例4
输入：
"ab",""
返回值：
"-1"
思路分析：
求解两个字符串 s1 和 s2 的最长公共子序列（Longest Common Subsequence, LCS）的问题。最长公共子序列是指两个序列共有的子序列中长度最长的那一个，但它不一定要求连续。这个问题是动态规划的一个经典应用。
- 初始化变量：
len1和len2分别表示字符串s1和s2的长度。- 创建一个二维数组
dp，大小为(len1 + 1) x (len2 + 1)。dp[i][j]用于存储s1的前i个字符和s2的前j个字符之间的最长公共子序列。注意，这里使用String[][]而不是通常的int[][]，因为我们需要直接存储子序列的字符串形式，而不是仅仅存储长度。 - 当
i == 0或j == 0时，即任一字符串为空时，最长公共子序列显然为空字符串""。因此，初始化dp数组的第一行和第一列为空字符串。
- 状态转移：
- 遍历
s1和s2的所有字符（从索引 1 开始，因为索引 0 已经初始化为空字符串）。 - 如果当前字符相等（
s1.charAt(i - 1) == s2.charAt(j - 1)），则最长公共子序列可以通过将当前字符添加到dp[i-1][j-1]的结果上来得到。这是因为当前字符在两个字符串中都出现，所以它可以被添加到之前的最长公共子序列中。 - 如果当前字符不相等，则最长公共子序列要么是
dp[i-1][j]（即不考虑s1的当前字符），要么是dp[i][j-1]（即不考虑s2的当前字符），取决于哪一个更长。
- 遍历
- 返回结果：
- 最终，
dp[len1][len2]存储了整个s1和s2的最长公共子序列。如果结果为空字符串（理论上不会发生，除非输入就是空字符串），则返回"-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) {int len1 = s1.length(), len2 = s2.length();// 明确状态: 当前需要处理的s1和s2分别前i和前j个元素// dp[i][j]表示从左到右，当处理到s1的第i个元素和s2的第j个元素时的公共子序列String[][] dp = new String[len1 + 1][len2 + 1];//当i==0或j==0的情况，dp[i][j]为""，因为空字符串没有公共子序列for (int i = 0; i <= len1; i++) {// j == 0dp[i][0] = "";}for (int j = 0; j <= len2; j++) {// i == 0dp[0][j] = "";}// 状态转移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];}
}