最长公共子序列

阳光穿透心脏的1/2处 2022-12-09 04:57 221阅读 0赞

# 最长公共子序列 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/longest-common-subsequence/

## 2、题目要求 ##

> **题目描述**

给定两个字符串 `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。

## 3、代码思路 ##

二维动态规划

1.  最长公共子序列（`Longest Common Subsequence`，简称 `LCS`）典型的解法是二维动态规划，还是老问题：为啥这个问题就是动态规划来解决呢？因为暴力解法时间复杂度太恐怖了，对于子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝。
2.  动态规划是将大问题分解为子问题，其关键就是我们如何定义子问题，如何定义 `dp[]` 数组的含义。为了方便起见，我们暂时认为 `dp[][]` 数组的索引和字符串的索引从 `1` 开始。我们定义 `dp[i][j]` 为 `text1[1...i]` 与 `text2[1...j]` 的最长公共子序列长度，那么我们只需要得到 `dp[text1.length][text2.length]` 即可求得 `LCS` 的长度
3.  为什么要将 `dp[0][]` 和 `dp[][0]` 留空？在动态规划中，我们一般将 `dp[0][]`(第一行) 和 `dp[][0]`(第一列) 作为初始条件，在本题中的含义为：空字符串 `""` 与任何字符串的 `LCS` 长度均为 `0`
4.  那么状态转移方程怎么推导呢？首先，我们需要明确两个 `for` 循环是必不可少的，因为我们需要分别遍历 `text1` 和 `text2` 才能求出 `dp[i][j]`，外层循环遍历 `text1` 字符串：`for (int i = 1; i <= text1Length; i++) {`，内层循环遍历 `text2` 字符串：`for (int j = 1; j <= text2Length; j++) {`。看下面的图(来自 [labuladong][])，如果 `text1.charAt(i - 1) == text2.charAt(j - 1)`，证明以 `text1[i-1]` 与 `text2[j-1]` 结尾能构成公共子序列(索引从 `0` 开始)，则 `text1[1..i]` 与 `text2[1..j]` 的最长公共子序列长度应该等于【`text1[1..i-1]` 与 `text2[1..j-1]` 的最长公共子序列长度 + `1`】(索引从 `1` 开始)；否则 `text1[1..i]` 与 `text2[1..j]` 的最长公共子序列长度应该等于【`Math.max(text1[1..i-1] 与 text2[1..j] 的最长公共子序列长度, text1[1..i] 与 text2[1..j-1] 的最长公共子序列长度)`】
5.  打完收工，睡觉

![image-20200921225646627][]

## 4、代码实现 ##

代码

class Solution {
        
            public int longestCommonSubsequence(String text1, String text2) {
        
                int text1Length = text1.length();
                int text2Length = text2.length();
                //  dp[i][j] 为 text1[1...i] 与 text2[1...j] 的最长公共子序列长度
                // 将 dp[0][](第一行) 和 dp[][0](第一列) 作为初始条件
                int[][] dp = new int[text1Length + 1][text2Length + 1];
    
                // 外层循环遍历 text1 字符串
                for (int i = 1; i <= text1Length; i++) {
        
                    // 内层循环遍历 text2 字符串
                    for (int j = 1; j <= text2Length; 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]);
                        }
                    }
                }
    
                // 返回两个字符串的 LCS长度
                return dp[text1Length][text2Length];
            }
        }

[labuladong]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/
[image-20200921225646627]: /images/20221123/9635c79df9c1489b881f9ac417e1a189.png