2021-02-06 | 1143. 最长公共子序列

以你之姓@ 2022-11-03 10:58 124阅读 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`
 *  输入的字符串只含有小写英文字符。

### 2. 解题思路 ###

这道题目的解法就是典型的**二维动态规划问题：**

*  首先初始化一个dp二维数组，通常情况下，数组定义时会比两个字符串的长度多1，这样每个元素的index都是有效的，不需要进行判断
 *  将dp数组中的每个元素都初始化为0，dp数组保存的是当前组合的状态，也就是当前最长的公共子序列的长度
 *  最后就是动态规划过程，如果当前索引对应的两个元素相等，那么就加一，如果不相等，就取它上面或者左面的元素的最大值

下面是示例的图示：

**复杂度分析：**

*  时间复杂度：O(mn)，其中m和n分别是两个字符串的长度，我们需要遍历元素个位为m+n的数组；
 *  时间复杂度：O(mn)，其中m和n分别是两个字符串的长度，我们需要初始化一个元素个位为m+n的dp数组；

### 3. 代码实现 ###

/** * @param {string} text1 * @param {string} text2 * @return {number} */
    var longestCommonSubsequence = function(text1, text2) { 
        const m = text1.length, n = text2.length, dp = []
        if(!m || !n){ 
            return 0
        }
        for (let i = 0; i <= m; i++) { 
            dp.push(new Array(n + 1).fill(0))
        }
    
        for (let i = 1; i <= m; i++) { 
            for (let 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]
    };

### 4. 提交结果 ###

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

[20210227183537654.png]: /images/20221024/0e2b3f0eb6ec48c48db73777a2f42a1e.png?