1143.最长公共子序列

链接：1143.最长公共子序列
难度：Medium
标签：字符串、动态规划
简介：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

题解 1 - typescript

• 编辑时间：2021-04-03
• 执行用时：136ms
• 内存消耗：50.7MB
• 编程语言：typescript
• 解法介绍：动态规划。

function longestCommonSubsequence(text1: string, text2: string): number {
  const len1 = text1.length;
  const len2 = text2.length;
  const dp = new Array(len1 + 1).fill(0).map(_ => new Array(len2 + 1).fill(0));
  for (let i = 0; i < len1; i++) {
    for (let j = 0; j < len2; j++) {
      dp[i + 1][j + 1] =
        text1[i] === text2[j] ? dp[i][j] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]);
    }
  }
  return dp[len1][len2];
}

题解 2 - javascript

• 编辑时间：2020-05-11
• 执行用时：92ms
• 内存消耗：57.5MB
• 编程语言：javascript
• 解法介绍：动态规划，递推。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  const len1 = text1.length;
  const len2 = text2.length;
  const dp = [];
  for (let i = 0; i <= len1; i++) {
    dp[i] = [];
    for (let j = 0; j <= len2; j++) if (i === 0 || j === 0) dp[i][j] = 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];
};

题解 3 - javascript

• 编辑时间：2020-05-11
• 执行用时：64ms
• 内存消耗：35.6MB
• 编程语言：javascript
• 解法介绍：根据题解 2，利用&1 取代%2。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  const len1 = text1.length;
  const len2 = text2.length;
  const dp = [];
  for (let i = 0; i < 2; i++) {
    dp[i] = [];
    for (let j = 0; j <= len2; j++) if (i === 0 || j === 0) dp[i][j] = 0;
  }
  let compI, preCompI;
  for (let i = 1; i <= len1; i++) {
    compI = i & 1;
    preCompI = (i - 1) & 1;
    for (let j = 1; j <= len2; j++)
      if (text1[i - 1] === text2[j - 1]) dp[compI][j] = dp[preCompI][j - 1] + 1;
      else dp[compI][j] = Math.max(dp[preCompI][j], dp[compI][j - 1]);
  }
  return dp[len1 & 1][len2];
};

题解 4 - typescript

• 编辑时间：2021-09-10
• 执行用时：108ms
• 内存消耗：51.8MB
• 编程语言：typescript
• 解法介绍：动态规划。

function longestCommonSubsequence(text1: string, text2: string): number {
  const len1 = text1.length;
  const len2 = text2.length;
  const dp = new Array(len1 + 1).fill(0).map(_ => new Array(len2 + 1).fill(0));
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      dp[i][j] = Math.max(
        dp[i - 1][j],
        dp[i][j - 1],
        dp[i - 1][j - 1] + (text1[i - 1] === text2[j - 1] ? 1 : 0)
      );
    }
  }
  return dp[len1][len2];
}

题解 5 - javascript

• 编辑时间：2020-05-11
• 执行用时：76ms
• 内存消耗：35.1MB
• 编程语言：javascript
• 解法介绍：根据题解 1，利用滚动数组优化空间。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  const len1 = text1.length;
  const len2 = text2.length;
  const dp = [];
  for (let i = 0; i < 2; i++) {
    dp[i] = [];
    for (let j = 0; j <= len2; j++) if (i === 0 || j === 0) dp[i][j] = 0;
  }
  for (let i = 1; i <= len1; i++) {
    const compI = i % 2;
    const preCompI = (i - 1) % 2;
    for (let j = 1; j <= len2; j++)
      if (text1[i - 1] === text2[j - 1]) dp[compI][j] = dp[preCompI][j - 1] + 1;
      else dp[compI][j] = Math.max(dp[preCompI][j], dp[compI][j - 1]);
  }
  return dp[len1 % 2][len2];
};

题解 6 - javascript

• 编辑时间：2020-05-12
• 执行用时：72ms
• 内存消耗：35.1MB
• 编程语言：javascript
• 解法介绍：根据题解 2，利用一维数组替代二维数组。

/**
 * @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(Math.max(len1, len2) + 1).fill(0);
  let leftTop = 0,
    replace = 0;
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      replace = text1[i - 1] === text2[j - 1] ? leftTop + 1 : Math.max(dp[j], dp[j - 1]);
      leftTop = dp[j];
      dp[j] = replace;
    }
    leftTop = dp[0];
  }
  return dp[len2];
};