1143. Longest Common Subsequence

2021-12-07  本文已影响0人  jluemmmm

给定两个字符串,返回两个字符串的最长公共子序列,如果不存在公共子序列,返回0。

子序列是指,是由原字符串在不改变相对顺序的情况下删除某些字符(或不删除字符后)组成的新字符串。

动态规划

dp[i][j] 表示s1[0, i]和s2[0, j]的最长公共子序列。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
  const m = text1.length + 1;
  const n = text2.length + 1;
  const dp = new Array(m).fill().map(i => Array(n).fill(0));
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; 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[m - 1][n - 1];
};
上一篇 下一篇

猜你喜欢

热点阅读