1143. Longest Common Subsequence

Leetcode link

题目简介

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */

题目给我们两个字符串 text1 与 text2

要求我们找到两个字符串的最长公共子序列

子序列指的是字符串在删除某些元素后，且不改变元素顺序的情况下产生的新字符串

解题思路

我们可以用 dp 的思路来做这道题

dp 数组是一个二位数组，dp[i][j] 用来记录 text1[0..i] 与 text2[0..j] 的最长公共子序列长度

转移方程如下：

• 如果 text1[i] === text2[j]，dp[i][j] = dp[i-1][j-1]+1
• 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1])

为了方便计算，我们给 dp 加一行一列并初始化为 0

Javascript

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    const len1 = text1.length
    const len2 = text2.length
    const dp = Array.from({ length: len1 + 1 }, _ => new Array(len2 + 1).fill(0))

    for (let row = 1; row <= len1; row++) {
        for (let col = 1; col <= len2; col++) {
            if(text1[row-1] === text2[col-1]) {
                dp[row][col] = dp[row - 1][col - 1] + 1
            } else {
                dp[row][col] = Math.max(dp[row][col - 1], dp[row - 1][col])
            }
        }
    }
    return dp[len1][len2]
};