1143. Longest Common Subsequence

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

Question

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde". A common subsequence of two strings is a subsequence that is common to both strings.

递归法

这里的find(i, j)，代表text1[i..]和text[j..]之间的lcs。

这个明确了之后，问题就会清晰很多：

• 明确状态：转移的状态应该是位置i,j
• 确定函数定义：find(i, j)，代表text1[i..]和text[j..]之间的lcs。
• 明确选择：
  • 如果text1[i]和text[j]，那么lcs肯定可以基于find(i - 1, j - 1)+1的
  • 如果不相等，在离他最近的子集中取最大值
• 明确base case：当到最后一个字符时，肯定是不存在lcs的，返回0

/**
 * 递归+备忘录
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    const cache = {};
    const getCacheData = (i, j) => {
        const key = `${[i, j]}`;
        if (cache[key] === undefined) cache[key] = find(i, j);
        return cache[key];
    };
    const find = (i, j) => {
        if (i === text1.length) return 0;
        if (j === text2.length) return 0;
        if (text1[i] === text2[j]) return getCacheData(i + 1, j + 1) + 1;
        else return Math.max(getCacheData(i + 1, j), getCacheData(i, j + 1), getCacheData(i + 1, j + 1));
    };
    return find(0, 0);
};

动态规划

dp类似：

/**
 * dp
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    const dp = new Array(text1.length + 1).fill().map(() => new Array(text2.length + 1).fill(0));
    for (let i = text1.length - 1; i >= 0; i--) {
        for (let j = text2.length - 1; j >= 0; j--) {
            if (text1[i] === text2[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
            else dp[i][j] = Math.max(dp[i][j + 1], dp[i + 1][j]);
        }
    }
    return dp[0][0];
};

End

明确好i和j的定义，对于这种类型的题目要有熟练度。