题目描述

Longest Common Subsequence

给定两个字符串 text1和 text2, 返回他们的最长公共子序列的长度。
子序列的定义：从源字符串中产生，可以与源字符串相同，也可以是只删除一些字符，剩下字符保持顺序不变产生的新字符串。
eg："ace" 是 "abcde"的子序列，但 "aec" 不是。
公共子序列： 即两个字符串含有的相同的子序列

如果不存在公共子序列不存在， 返回 0

eg：

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Input: text1 = "ghbrgc", text2 = "hcbgcrcbh"
Output: 4
Explanation: The longest common subsequence is "hbgc" and its length is 4.

另：

• 输入字符串均为英文小写字符
• 字符串长度区间满足 [1, 1000]

From leetcode No.1143 Medium (opens new window)

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    
};

解法

点击查看

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

    const dp = new Array(len1 + 1)
    dp[0] = new Array(len2 + 1).fill(0)

    for (let i = 0; i < len1; i++) {
        dp[i+1] = new Array(len2 + 1).fill(0)
        for (let j = 0; j < len2; j++) {
            if (text1[i] === text2[j])
                dp[i+1][j+1] = dp[i][j] +1
            else
                dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j])
        }
    }
    return dp[len1][len2]
};

总结

还是先找规律，确定状态转移方程
eg: 以text1, text2 均为abc为例
dp为一个二维数组，dp[i][j] 表示 text1的 [0, i]个元素 与text2的 [0, j]个元素的LCS (longestCommonSubsequence)
eg: dp[1][2] 及表示 ab 与 abc的 LCS, 对应的值为 2

所有情况具体为下图

	a	b	c
a	1	1	1
b	1	2	2
c	1	2	3

可以得到：

• dp[i][j]的最小值为 0
• 当 text1[i] == text2[j]时， dp[i][j] = dp[i-1][j-1] + 1
• 当 text1[i] != text2[j]时, dp[i][j] = Math.max(dp[i-1][j], dp[1][j-1])

由此便可得出递归规律

var longestCommonSubsequence = function (text1, text2) {
    const len1 = text1.length
    const len2 = text2.length
    function lcs(len1, len2) {
        if (len1 === -1 || len2 === -1) //原始状态
            return 0
        if (text1[len1] === text2[len2])
            return lcs(len1 - 1, len2 - 1) + 1
        else
            return Math.max(lcs(len1 - 1, len2), lcs(len1, len2 - 1))
    }
    return lcs(len1 - 1, len2 - 1)
};

但是递归调用栈次数太多，存在重复计算，于是可以用动态规划空间换时间的方案

学习提交中最快的解法：

点击查看

var longestCommonSubsequence = function(text1, text2) {
    const n1 = text1.length;
    const n2 = text2.length;
    
    let dp = new Array(n2 + 1).fill(0);
    let pre = 0;
    
    for (let i = 1; i <= n1; ++i) {
        pre = 0;
        for (let j = 1; j <= n2; ++j) {
            const tmp = dp[j];
            if (text1[i - 1] == text2[j - 1]) {
                dp[j] = pre + 1;
            } else {
                dp[j] = Math.max(dp[j - 1], dp[j]);   
            }
            pre = tmp;
        }
    }
    return dp[n2];
};

• 时间复杂度不变，但是空间复杂度大大降低，且 dp的思想更加纯粹

参考

• longest-common-subsequence (opens new window)