1143.md

Leetcode 1143. 最长公共子序列

1143. 最长公共子序列

动态规划：

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  // 计算两个字符串的长度，避免后面重复获取
  const text1Length = text1.length;
  const text2Length = text2.length;

  // 初始化二维数组，用于保存每次计算的值，避免重复计算
  let dp = new Array(text1Length + 1).fill(0);
  dp = dp.map(() => new Array(text2Length + 1).fill(0));

  // 核心思路:
  // text1 = "abcde", text2 = "ace"
  // "abcde" 最后一个字符 e === "ace" 最后一个字符 e，那么最长公共子序列 = longestCommonSubsequence("abcd", "ac") + 1
  // "abcd" 最后一个字符 d !== "ac" 最后一个字符 c，那么最长公共子序列 = Math.max(longestCommonSubsequence("abcd", "a"),longestCommonSubsequence("abc", "ac"));
  for (let i = 1; i <= text1Length; i++) {
    for (let j = 1; j <= text2Length; 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]);
      }
    }
  }
  console.log(dp);

  return dp[text1Length][text2Length]; // 返回最后一个数组的最后一个值
};

console.log(longestCommonSubsequence("abcde", "ace"))