后端开发刷题 | 最长公共子序列（非连续）

描述

给定两个字符串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）的问题。最长公共子序列是指两个序列共有的子序列中长度最长的那一个，但它不一定要求连续。这个问题是动态规划的一个经典应用。

1. 初始化变量：
   • len1 和 len2 分别表示字符串 s1 和 s2 的长度。
   • 创建一个二维数组 dp，大小为 (len1 + 1) x (len2 + 1)。dp[i][j] 用于存储 s1 的前 i 个字符和 s2 的前 j 个字符之间的最长公共子序列。注意，这里使用 String[][] 而不是通常的 int[][]，因为我们需要直接存储子序列的字符串形式，而不是仅仅存储长度。
   • 当 i == 0 或 j == 0 时，即任一字符串为空时，最长公共子序列显然为空字符串 ""。因此，初始化 dp 数组的第一行和第一列为空字符串。
2. 状态转移：
   • 遍历 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 的当前字符），取决于哪一个更长。
3. 返回结果：
   • 最终，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 == 0
            dp[i][0] = "";
        }
        for (int j = 0; j <= len2; j++) {
            // i == 0
            dp[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];
    }
}