最长公共子序列、最长重复子数组、最长公共前缀

最长公共子序列

题目描述

示例：

输入：text1 = "abcde", text2 = "ace"

输出：3

解释：最长公共子序列是 "ace"，它的长度为 3。

思路

1. 如果 text1[i - 1] === text2[j - 1]，表示当前字符相等，最长子序列 +1

2. 否则表示字符不相等，只能从前一个子问题里选一个最长的

题解

tsCopy
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length,
    n = text2.length;
  const dp = Array.from({ length: m + 1 }).map(() => new Array(n + 1).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][j - 1], dp[i - 1][j]);
      }
    }
  }

  return dp[m][n];
}

最长重复子数组

题目描述

示例：

输入：nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7]

输出：3

解释：长度最长的公共子数组是 [3, 2, 1]。

思路

1. 数组要求连续，而子序列不要求连续

2. dp 的定义

题解

tsCopy
function findLength(nums1: number[], nums2: number[]): number {
  let maxLen = 0,
    dp = Array.from({ length: nums1.length + 1 }, () =>
      new Array(nums2.length + 1).fill(0)
    );

  for (let i = 1; i <= nums1.length; i++) {
    for (let j = 1; j <= nums2.length; j++) {
      if (nums1[i - 1] === nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLen = Math.max(maxLen, dp[i][j]);
      }
    }
  }

  return maxLen;
}

最长公共前缀

题目描述

示例：

输入：strs = ["flower", "flow", "flight"]

输出："fl"

思路

题解

tsCopy
function longestCommonPrefix(strings: string[]): string {
  if (strings.length === 0) return "";

  const firstWord = strings[0];

  for (let charIndex = 0; charIndex < firstWord.length; charIndex++) {
    const currentChar = firstWord[charIndex];

    for (let wordIndex = 1; wordIndex < strings.length; wordIndex++) {
      const currentWord = strings[wordIndex];

      // 越界或字符不一致
      if (
        charIndex >= currentWord.length ||
        currentWord[charIndex] !== currentChar
      ) {
        return firstWord.substring(0, charIndex);
      }
    }
  }

  // 所有字符都匹配，返回整个第一个单词
  return firstWord;
}