题解 | 最长公共子序列(二)

import java.util.*;


public class Solution {
    /**
     * 寻找两个字符串的最长公共子序列(Longest Common Subsequence, LCS)
     *
     * @param s1 第一个字符串
     * @param s2 第二个字符串
     * @return 返回找到的最长公共子序列，如果没有公共子序列则返回"-1"
     */
    public String LCS(String s1, String s2) {
        // 检查输入字符串是否为空或长度为0
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return "-1";
        }

        // 获取两个字符串的长度
        int m = s1.length();
        int n = s2.length();
        // 创建二维数组dp，用于存储中间结果
        String[][] dp = new String[m + 1][n + 1];


        /**
         * 初始化动态规划数组的第一行和第一列
         * 将dp[i][0]和dp[0][j]设置为空字符串，表示当一个字符串为空时，最长公共子序列为空
         */
        for (int i = 0; i <= m; i++) {
            dp[i][0] = "";
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = "";
        }

        /**
         * 使用动态规划填充数组
         * 遍历两个字符串的所有字符组合，计算最长公共子序列
         */
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果当前字符匹配，则将当前字符添加到之前的最长公共子序列中
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
                } else {
                    // 如果当前字符不匹配，则选择上方或左侧较长的子序列
                    String temp1String = dp[i - 1][j];
                    String temp2String = dp[i][j - 1];
                    dp[i][j] = temp1String.length() > temp2String.length() ? temp1String : temp2String;
                }
            }
        }

        /**
         * 获取最终结果
         * 如果结果字符串长度大于0，则返回该字符串；否则返回"-1"
         */
        String res = dp[m][n];
        return res.length() > 0 ? res : "-1";
    }

}