小学生都能看懂的题解 | #最长公共子序列(二)#

解释思路

想象一下，我们有两个单词串（也就是字符串），我们要找出它们共有的最长的部分，这个部分中的字母顺序在两个字符串中都是一样的，但是它们不需要连续出现。

步骤分解：

1. 比较字符：我们从每个字符串的第一个字母开始比较，看看它们是不是一样的。
2. 标记相同点：如果字母一样，我们就记下来，然后继续比较后面的字母。
3. 记录最长序列：我们一直这样做，直到找出最长的一串相同的字母序列。
4. 没有共同字母的情况：如果完全找不到相同的字母，我们就说这两个字符串没有公共子序列。

代码实现

现在，让我们把这个想法变成一个简单的Java方法 LCS，它接受两个字符串 s1 和 s2 作为参数，并返回它们的最长公共子序列。

public class LongestCommonSubsequence {
    // 这个方法用来找到两个字符串的最长公共子序列
    public String LCS(String s1, String s2) {
        int length1 = s1.length(); // 获取第一个字符串的长度
        int length2 = s2.length(); // 获取第二个字符串的长度
        
        // 创建一个表格来记录我们找到的公共子序列长度
        int[][] table = new int[length1 + 1][length2 + 1];

        // 遍历两个字符串的所有字符
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                // 如果当前字符相同
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    // 就把这个字符加入到已知的最长公共子序列后面
                    table[i][j] = table[i - 1][j - 1] + 1;
                } else {
                    // 如果字符不同，取两者之间最长的那个
                    table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
                }
            }
        }

        // 从表格中读取最长公共子序列
        StringBuilder result = new StringBuilder();
        for (int i = length1, j = length2; i != 0 && j != 0; ) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                result.insert(0, s1.charAt(i - 1));
                i--;
                j--;
            } else if (table[i - 1][j] > table[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // 如果结果为空，返回 "-1"
        return result.length() == 0 ? "-1" : result.toString();
    }
}

如何理解代码

这段代码创建了一个表格（也就是一个二维数组），用来存储在查找过程中遇到的最长公共子序列的长度。我们通过比较两个字符串中的字符，并更新这个表格，最后再根据表格中的信息重建最长公共子序列。如果没有公共子序列，就返回 -1。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。