小学生都能看懂的题解 | #最长公共子串#

解释思路

想象一下，你有两个单词串（即字符串），我们要找出它们共有的最长的一部分，这部分必须是连续的字符。

步骤分解：

1. 初始化：我们需要一个表格来记录我们找到的最长公共子串的长度。
2. 比较字符：我们从每个字符串的第一个字母开始比较，看看它们是不是一样的。
3. 标记相同点：如果字符相同，我们就记录这个长度，并继续比较后面的字符。
4. 记录最长序列：我们一直这样做，直到找出最长的一段连续相同的字符。
5. 返回结果：最后，我们根据记录的信息，找出最长的公共子串并返回。

Java 方法实现

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

public class LongestCommonSubstring {
    // 这个方法用来找到两个字符串的最长公共子串
    public String LCS(String str1, String str2) {
        int len1 = str1.length(); // 获取第一个字符串的长度
        int len2 = str2.length(); // 获取第二个字符串的长度

        // 创建一个表格来记录我们找到的最长公共子串的长度
        int[][] dp = new int[len1 + 1][len2 + 1];

        // 初始化最大长度为 0
        int maxLength = 0;
        // 初始化最长公共子串的起始索引
        int startIndex = 0;

        // 填充状态转移表
        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;
                    // 更新最大长度和起始索引
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        startIndex = i - 1; // 注意这里的索引调整
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        // 返回最长公共子串
        return str1.substring(startIndex - maxLength + 1, startIndex + 1);
    }
}

如何理解代码

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

具体步骤如下：

1. 初始化表格：创建一个 (len1 + 1) x (len2 + 1) 的二维数组 dp。
2. 填充表格：对于 str1 和 str2 的每一个字符，如果它们相同，就在 dp 表格中记录当前最长公共子串的长度，并更新最大长度和起始索引。
3. 返回结果：根据记录的最大长度和起始索引，从 str1 中截取出最长公共子串。

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