1. 题目描述

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

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

示例 1:

  1. 输入：text1 = "abcde", text2 = "ace" 
  2. 输出：3  
  3. 解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

  1. 输入：text1 = "abc", text2 = "abc"
  2. 输出：3
  3. 解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

  1. 输入：text1 = "abc", text2 = "def"
  2. 输出：0
  3. 解释：两个字符串没有公共子序列，返回 0。

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000

  • 输入的字符串只含有小写英文字符。

    2. 解题思路

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

  • 首先初始化一个dp二维数组，通常情况下，数组定义时会比两个字符串的长度多1，这样每个元素的index都是有效的，不需要进行判断

  • 将dp数组中的每个元素都初始化为0，dp数组保存的是当前组合的状态，也就是当前最长的公共子序列的长度
  • 最后就是动态规划过程，如果当前索引对应的两个元素相等，那么就加一，如果不相等，就取它上面或者左面的元素的最大值

下面是示例的图示：

null a b c d e
null
a 1 1 1 1 1
c 1 1 2 2 2
e 1 1 2 2 3

复杂度分析：

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

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

    3. 代码实现

    1. /**
    2. * @param {string} text1
    3. * @param {string} text2
    4. * @return {number}
    5. */
    6. var longestCommonSubsequence = function(text1, text2) {
    7.   const m = text1.length, n = text2.length, dp = []
    8.   if(!m || !n){
    9.       return 0
    10.   }
    11.   for (let i = 0; i <= m; i++) {
    12.       dp.push(new Array(n + 1).fill(0))
    13.   }
    15.   for (let i = 1; i <= m; i++) {
    16.       for (let j = 1; j <= n; j++) {
    17.           if (text1.charAt(i - 1) === text2.charAt(j - 1)) {
    18.               dp[i][j] = dp[i - 1][j - 1] + 1
    19.           } else {
    20.               dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
    21.           }
    23.       }
    24.   }
    25.   return dp[m][n]
    26. };

    4. 提交结果

    image.png