1143. 最长公共子序列——【Leetcode每日刷题】

ゞ浴缸里的玫瑰 2024-03-25 09:56 42阅读 0赞

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

给定两个字符串 text1 和 text2，返回这两个字符串的最长 **公共子序列** 的长度。如果不存在 **公共子序列** ，返回 0 。

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

*  例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的 **公共子序列** 是这两个字符串所共同拥有的子序列。

##### 示例 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, text2.length <= 1000
 *  text1 和 text2 仅由小写英文字符组成。

#### 思路：(动态规划) ####

对于两个子序列  S 1 S1 S1 和  S 2 S2 S2，找出它们最长的公共子序列。

定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp\[i\]\[j\] 表示  S 1 S1 S1 的前 i 个字符与  S 2 S2 S2 的前 j 个字符最长公共子序列的长度。考虑  S 1 i S1\_i S1i与  S 2 j S2\_j S2j 值是否相等，分为两种情况：

*  当  S 1 i = = S 2 j S1\_i == S2\_j S1i==S2j 时，那么就能在  S 1 S1 S1 的前 i -1 个字符与  S 2 S2 S2 的前 j -1 个字符最长公共子序列的基础上再加上  S 1 i S1\_i S1i 这个值，最长公共子序列长度加 1，即 dp\[i\]\[j\] = dp\[i-1\]\[j-1\] + 1。
 *  当  S 1 i ! = S 2 j S1\_i != S2\_j S1i!=S2j 时，此时最长公共子序列为  S 1 S1 S1的前 i -1 个字符和 S2 的前 j 个字符最长公共子序列，或者  S 1 S1 S1 的前 i 个字符和  S 2 S2 S2 的前 j -1 个字符最长公共子序列，取它们的最大者，即 dp\[i\]\[j\] = max\{ dp\[i-1\]\[j\], dp\[i\]\[j-1\] \}。

综上，最长公共子序列的 **状态转移方程** 为：

d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j − 1 \] + 1 S 1 i = = S 2 j max ⁡ ( d p \[ i − 1 \] \[ j \] , d p \[ i \] \[ j − 1 \] ) S 1 i < > S 2 j d p\[i\]\[j\]=\\left\\\{\\begin\{array\}\{rr\} d p\[i-1\]\[j-1\]+1 & S 1\_\{i\}==S 2\_\{j\} \\\\ \\max (d p\[i-1\]\[j\], d p\[i\]\[j-1\]) & S 1\_\{i\}<>S 2\_\{j\} \\end\{array\}\\right. dp\[i\]\[j\]=\{ dp\[i−1\]\[j−1\]\+1max(dp\[i−1\]\[j\],dp\[i\]\[j−1\])S1i==S2jS1i<>S2j

对于长度为 m 的序列 S1 和长度为 n 的序列 S2，dp\[m\]\[n\] 就是序列 S1 和序列 S2 的最长公共子序列长度。

与**最长递增子序列** 相比，最长公共子序列有以下不同点：

*  针对的是两个序列，求它们的最长公共子序列。
 *  在最长递增子序列中，dp\[i\] 表示以  S i S\_i Si 为结尾的最长递增子序列长度，子序列必须包含  S i S\_i Si ；在最长公共子序列中，dp\[i\]\[j\] 表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度，不一定包含  S 1 i S1\_i S1i 和  S 2 j S2\_j S2j。
 *  在求最终解时，最长公共子序列中 dp\[m\]\[n\] 就是最终解，而最长递增子序列中 dp\[n\] 不是最终解，因为以  S n S\_n Sn 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。

#### 代码：(Java) ####

public class LongestCommonSubsequence {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		String text1 = "abcde";
    		String text2 = "ace";
    		System.out.println(longestCommonSubsequence(text1,text2));
    	}
    	public static int longestCommonSubsequence(String text1, String text2) {
        
    		int m = text1.length();
    		int n = text2.length();
    		
    		int[][] dp = new int[m + 1][n + 1];
    		
    		for(int i = 1; i <= m; i++) {
        
    			for(int j = 1; j <= n; j++) {
        
    				if(text1.charAt(i - 1) == text2.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[m][n];
        }
    }

##### 运行结果： #####

![在这里插入图片描述][8322ab2822344c53ac1116bc373c21a1.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( m n ) O(mn) O(mn)，需要遍历两个字符串。
 *  **空间复杂度**： O ( m n ) O(mn) O(mn)，需要m\*n的二维数组。

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[8322ab2822344c53ac1116bc373c21a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/aef9f43005994d43b26d228411eed9cc.png
[Link 1]: https://leetcode.cn/problems/longest-common-subsequence/