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

最长公共子序列

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例：

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

输出：3

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

思路

属于字符串动态规划问题。

dp[i][j]：text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。

初始化：

dp[0][*] = 0 & dp[*][0] = 0：任何字符串和空串的公共子序列都是 0

状态转移方程：

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

也就是 dp[i][j] = dp[i - 1][j - 1] + 1

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

也就是 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

题解

ts
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 和 nums2，返回两个数组中公共的、长度最长的子数组的长度。

示例：

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

输出：3

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

思路

和最长公共子序列的不同：

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

所以在 nums1[i - 1] !== nums2[j - 1] 时，子序列会取上一个子问题的最大值；而子数组是直接置 dp[i][j] 为 0，具体在代码里就是直接跳过不处理

dp 的定义

最长重复子序列的 dp[i][j]：前 i 与前 j 的最长重复子序列，因此最终答案就存在 dp[m][n] 中。

最长重复子数组的 dp[i][j]：以 A[i-1] 和 B[j-1] 结尾的最长公共子数组长度。

为什么不能直接返回 dp[m][n]：因为最长重复子数组里 dp[i][j] 的值只表示以 i 和 j 结尾时的子数组长度，所以 dp[m][n] 并不代表全局最大值。最大值可能出现在 dp 表的任意位置，因此需要手动维护 maxLen。

题解

ts
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"

思路

可以相当于比较一个二维数组的竖行是不是一致的

注意：外循环是 strs[0]，内循环才是 strs，因为是对每个字符进行逐行的比较

并且跳出条件除了字符不一致之外，还有该字符串走到头了

题解

ts
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;
}