1143. 最长公共子序列

1143. 最长公共子序列

1. 确定dp数组（dp table）以及下标的含义

   dp[i][j]: 表示在字符串 text1 下标 [0, 1] 区间选取一些字符串，在字符串 text2 下标 [0, j] 区间选取一些字符串，求得最长的公共子序列。

2. 确定递推公式

   case 1:
   	text1: ''
   	text2: 任意
   
   case 2:
   	text1: 'A'
   	text2: 任意
   
   case 3:
   	text1: '......A'
   	text2: '........A'
   

   case 3 中最后一个字符串是否相同？

   • 相同：那么只要求出 text1 和 text2 分别裁剪下最后一个字符串后剩下的字符串进行求最长公共子序列的计算 dp[i-1][j-1]，在加 1（当前字符串相同的）
   • 不同：那么需要
     • 用 text1 去除 最后一个字符串后的字符串和用 text2 没去除 最后一个字符串后的字符串
     • 用 text1 没去除 最后一个字符串后的字符串和用 text2 去除 最后一个字符串后的字符串

   递归公式：

   相同：dp[i][j] = dp[i - 1][j - 1] + 1;

   不相同：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])

3. dp数组如何初始化

   最初初始化为 0 即可，后续会进行覆盖。

4. 确定遍历顺序

   遍历顺序没有影响，下标都需要从 1 开始，二维数组长度为 [len1][len2]

5. 举例推导dp数组

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    let len1 = text1.length;
    let len2 = text2.length;

    let dp = new Array(len1 + 1).fill().map(item => new Array(len2 + 1).fill(0));

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if (text1[i - 1] === text2[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[len1][len2];
};

时间复杂度：O(len1 * len2)

空间复杂度：O(len1 * len2)