LeetCode：最长公共子序列

爱被打了一巴掌 2023-07-23 12:55 8阅读 0赞

##### 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
 *  输入的字符串只含有小写英文字符。

来源：力扣（LeetCode）  
原题传送门：[link][].

##### 2. 提取关键词 #####

二维数组，动态规划

##### 3. 思路 #####

1.  首先创建一个二维数组，其长度行宽为s1.length() + 1，列宽为s2.length() + 1；
2.  使用两个for循环遍历数组
3.  分两种情况向内添加值：  
    ![\*\*][20200408090549617.png]

解析传送门：[link][link 1].

##### 4. 代码（Java） #####

不使用辅助数组（查询速度较慢）

class Solution {
      public int longestCommonSubsequence(String s1, String s2) {
            int[][] dp = new int[s1.length() + 1][s2.length() + 1];                              
                 for(int i = 1 ; i < s1.length() + 1 ; i ++){
                for(int j = 1 ; j < s2.length()  + 1 ; j ++){
                    //如果末端相同
                    if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                        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[s1.length()][s2.length()];
        }
    }

使用辅助数组（查询速度快）

class Solution {
      public int longestCommonSubsequence(String text1, String text2) {
            char[] s1 = text1.toCharArray();
            char[] s2 = text2.toCharArray();
            int[][] dp = new int[s1.length + 1][s2.length + 1];
            for(int i = 1 ; i < s1.length + 1 ; i ++){
                for(int j = 1 ; j < s2.length + 1 ; j ++){
                    //如果末端相同
                    if(s1[i - 1] == s2[j - 1]){
                        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[s1.length][s2.length];
        }
    }

> 1.  **String string = “a,b,c”;**  
>     String \[\] stringArr= string.split(","); //注意分隔符知是需要转译滴…  
>     如果是"abc"这种字符串道,就直接
> 2.  **String string = “abc” ;**  
>     char \[\] stringArr = string.toCharArray(); //注意返回值是char数组回  
>     如果要返回byte数组就直接使用getBytes方法就答ok了~~
> 3.  **String string = “abc” ;**  
>     byte \[\] stringArr = string.getBytes();

##### 5.复杂度 #####

暂无

##### 6. 知识积累 #####

*  暂无

[link]: https://leetcode-cn.com/problems/longest-common-subsequence
[20200408090549617.png]: /images/20230528/ec01965db1ea4fe09d6f19b567e25613.png
[link 1]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/chao-xiang-xi-dong-tai-gui-hua-jie-fa-by-shi-wei-h/