1143.最长公共子序列

悠悠 2023-10-16 17:48 100阅读 0赞

#### 1143.最长公共子序列 ####

*  题干描述
 *  解题思路
 *   *  1. 确定dp数组（dp table）以及下标的含义
     *  2. 确定递推公式
     *  3. dp数组如何初始化
     *  4. 确定遍历顺序
     *  5. 举例推导dp数组
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

*  输入：text1 = “abcde”, text2 = “ace”
 *  输出：3
 *  解释：最长公共子序列是 “ace”，它的长度为 3。

示例 2:

*  输入：text1 = “abc”, text2 = “abc”
 *  输出：3
 *  解释：最长公共子序列是 “abc”，它的长度为 3。

示例 3:

*  输入：text1 = “abc”, text2 = “def”
 *  输出：0
 *  解释：两个字符串没有公共子序列，返回 0。

提示:

*  1 <= text1.length <= 1000
 *  1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。

## 解题思路 ##

本题和**动态规划：718. 最长重复子数组** 区别在于这里不要求是连续的了，但要有相对顺序，即：“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

继续动规五部曲分析如下：

### 1. 确定dp数组（dp table）以及下标的含义 ###

dp\[i\]\[j\]：长度为\[0, i - 1\]的字符串text1与长度为\[0, j - 1\]的字符串text2的最长公共子序列为dp\[i\]\[j\]

有同学会问：为什么要定义长度为\[0, i - 1\]的字符串text1，定义为长度为\[0, i\]的字符串text1不香么？

这样定义是为了后面代码实现方便，如果非要定义为长度为\[0, i\]的字符串text1也可以，我在 **动态规划：718. 最长重复子数组** 中的「拓展」里 详细讲解了区别所在，其实就是简化了dp数组第一行和第一列的初始化逻辑。

### 2. 确定递推公式 ###

主要就是两大情况： text1\[i - 1\] 与 text2\[j - 1\]相同，text1\[i - 1\] 与 text2\[j - 1\]不相同

如果text1\[i - 1\] 与 text2\[j - 1\]相同，那么找到了一个公共元素，所以dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1;

如果text1\[i - 1\] 与 text2\[j - 1\]不相同，那就看看text1\[0, i - 2\]与text2\[0, j - 1\]的最长公共子序列 和 text1\[0, i - 1\]与text2\[0, j - 2\]的最长公共子序列，取最大的。

即：dp\[i\]\[j\] = max(dp\[i - 1\]\[j\], dp\[i\]\[j - 1\]);

代码如下：

if (text1[i - 1] == text2[j - 1]) {
        
        dp[i][j] = dp[i - 1][j - 1] + 1;
    } else {
        
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }

### 3. dp数组如何初始化 ###

先看看dp\[i\]\[0\]应该是多少呢？

test1\[0, i-1\]和空串的最长公共子序列自然是0，所以dp\[i\]\[0\] = 0;

同理dp\[0\]\[j\]也是0。

其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。

### 4. 确定遍历顺序 ###

从递推公式，可以看出，有三个方向可以推出dp\[i\]\[j\]，如图：  
![在这里插入图片描述][e1e1198434634f54b74234063f5fa097.png]  
那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。

### 5. 举例推导dp数组 ###

以输入：text1 = “abcde”, text2 = “ace” 为例，dp状态如图：  
![在这里插入图片描述][a91cd879759a47c7bca5805697b6ae3e.png]  
最后红框dp\[text1.size()\]\[text2.size()\]为最终结果

## 代码实现 ##

class Solution {
        
        // 1143.最长公共子序列
        public int longestCommonSubsequence(String text1, String text2){
        
            // char[] char1 = text1.toCharArray();
            // char[] char2 = text2.toCharArray();
            // 可以在一开始的时候就先把text1, text2转成char[], 之后就不需要有这么多为了处理字串的调整
            int[][] dp = new int[text1.length() + 1][text2.length() + 1]; // 先对dp数组做初始化操作
            for(int i = 1; i <= text1.length(); i++){
        
                char char1 = text1.charAt(i - 1);
                for(int j = 1; j <= text2.length(); j++){
        
                    char char2 = text2.charAt(j - 1);
                    if(char1 == char2){
         // 开始列出状态转移方程
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else{
        
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[text1.length()][text2.length()];
        }
    }

**参考资料**：[代码随想录-1143.最长公共子序列][-1143.]

[Link 1]: https://leetcode.cn/problems/longest-common-subsequence/
[e1e1198434634f54b74234063f5fa097.png]: https://img-blog.csdnimg.cn/e1e1198434634f54b74234063f5fa097.png
[a91cd879759a47c7bca5805697b6ae3e.png]: https://img-blog.csdnimg.cn/a91cd879759a47c7bca5805697b6ae3e.png
[-1143.]: https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE