LC1143. 最长公共子序列

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 示例 1： 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。 示例 2： 输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。 提示： 1 <= text1.length, text2.length <= 1000 text1 和 text2 仅由小写英文字符组成。

题目解析

好的，没问题。我们一起来把这道题啃下来。

题目在说什么

这道题给了我们两个字符串，比如 text1 = "abcde" 和 text2 = "ace"。

我们要找到一个最长的、同时存在于这两个字符串里的子序列。

关键要理解什么是“子序列”：它不是必须连续的，但必须保持原来的顺序。比如 "ace" 是 "abcde" 的子序列，因为我们可以在 "abcde" 里挑出第1个字符 a、第3个字符 c、第5个字符 e，它们顺序没变，只是跳过了中间的 b 和 d。但 "aec" 就不是，因为在 "abcde" 里 e 在 c 后面，你没办法在不改变顺序的情况下先拿到 e 再拿到 c。

所以，这道题就是让我们找出两个字符串共同拥有的、最长的那个子序列的长度。在例子里，"ace" 就是答案，长度是3。

思路是怎么来的

想象一下，你面前有两本漫画书，你想找出它们共同拥有的、最长的连续剧情片段（但允许你跳着看，只要顺序对就行）。你会怎么比较？

最笨的办法：把第一本书的所有可能的子序列（剧情片段）都列出来，然后去第二本书里找，看哪个片段也在里面，并且最长。但一个字符串的子序列数量是指数级的，字符串一长，电脑就算到天荒地老。

我们需要一个更聪明的办法。

核心思想：化整为零，从最简单的情况开始推理。

我们不要一下子想两个完整的字符串。我们想想，如果只看两个字符串的开头一小部分，能不能知道它们的最长公共子序列长度？

比如，我们只看 text1 的第一个字符 a，和 text2 的第一个字符 a。它们相等，所以最长公共子序列长度就是1。

现在，我们增加一点难度。看 text1 的前两个字符 ab，和 text2 的第一个字符 a。b 和 a 不相等，所以最长公共子序列还是 a，长度是1。

再增加难度，看 text1 的前两个字符 ab，和 text2 的前两个字符 ac。

• 我们比较 text1 的最后一个字符 b 和 text2 的最后一个字符 c。它们不相等。
• 那么，最长公共子序列可能来自两种情况：

1. 不看 text1 的最后一个字符 b，只看 text1 的前1个字符 a 和 text2 的前2个字符 ac 的最长公共子序列。这个我们之前算过，是1（就是 a）。 2. 不看 text2 的最后一个字符 c，只看 text1 的前2个字符 ab 和 text2 的前1个字符 a 的最长公共子序列。这个我们也算过，也是1（还是 a）。

• 我们取这两种情况里最大的那个，所以 "ab" 和 "ac" 的最长公共子序列长度是1。

你看，我们通过解决更小、更简单的问题，一步步推导出了更大问题的答案。这就是动态规划的核心思想。

生活化比喻： 想象你有一张表格，行代表 text1 的前 i 个字符，列代表 text2 的前 j 个字符。表格里填的数字就是这两个前缀的最长公共子序列长度。我们一行一行、一列一列地填这个表格。填每个格子的时候，我们只需要看它左边、上边、左上角这三个已经填好的格子，以及当前比较的两个字符是否相等，就能决定这个格子的值。填完最后一个格子，答案就有了。

代码逐步拆解

现在我们来看代码是怎么实现这个填表过程的。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        
        // 1. 获取两个字符串的长度
        int m = text1.length();
        int n = text2.length();

        // 2. 创建我们的“表格”，也就是二维数组 dp
        // dp[i][j] 代表：text1 的前 i 个字符 和 text2 的前 j 个字符 的最长公共子序列长度
        // 注意：我们创建了 m+1 行和 n+1 列，因为我们要处理“前0个字符”这个情况
        int[][] dp = new int[m + 1][n + 1];
        
        // 3. 初始化表格的第一行和第一列
        // dp[0][0] = 0，表示前0个和前0个，没有字符，长度当然是0
        // dp[i][0] = 0，表示 text1 前 i 个字符和 text2 前 0 个字符，没有公共子序列，长度是0
        // dp[0][j] = 0，同理
        // 因为 Java 中 int 数组默认值就是0，所以这两步其实可以省略，但写出来更清晰
        dp[0][0] = 0;
        for( int i = 0 ; i <= m ; i++){
            dp[i][0] = 0;
        }
        for( int j = 0 ; j <= n ; j++){
            dp[0][j] = 0;
        }

        // 4. 开始填表！i 从1到m，j从1到n
        // 注意：i 代表 text1 的前 i 个字符，所以 text1 的第 i 个字符的索引是 i-1
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {