[1143] 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。

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

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde"的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

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

输出：3

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

示例 2:

输入：text1 = "abc", text2 = "abc"

输出：3

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

示例 3:

输入：text1 = "abc", text2 = "def"

输出：0

解释：两个字符串没有公共子序列，返回 0。

提示：

1 <= text1.length <= 1000

1 <= text2.length <= 1000

输入的字符串只含有小写英文字符。

最长公共子序列 (LCS) 是字符串动态规划里最经典的题型之一了，动态规划最重要的思想就是将题型转化为递归调用的子问题，并对子问题求解。

这里可以构建一个二维数组，横轴和纵轴分别为 text1 和 text2 的每一个字符，设 dp[i][j] 表示 text1.slice(0,i) 和 text2.slice(0,j) 的最大公共子序列。

在遍历过程中我们可以发现，当一个新字符加入字符串尾部进行比对时，有两种情况需要判断：

当 text1[i] === text2[j] 时，说明该字符一定在最长公共子序列中。此时更新最长公共子序列，更新为两字符串新增该字符之前的最长值 + 1。

dp[i][j] = dp[i-1][j-1] + 1

当 text1[i] !== text2[j] 时，意味着两个字符至少有一个不在最长子序列中。一共有三种情况，

1. text1[i] 不在，则此时情况跟 dp[i-1][j] 相同。
2. text2[j] 不在，则此时情况跟 dp[i][j-1] 相同。
3. 若都不在，则此时情况跟 dp[i-1][j-1] 相同。

由于字符不匹配，此时最长公共子序列不可能会有更新。因此只需要取上述三种情况的最大值即可。

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

function longestCommonSubsequence(text1: string, text2: string): number {
  const len1 = text1.length;
  const len2 = text2.length;
  const dp = Array(len1 + 1)
    .fill(0)
    .map(x => Array(len2 + 1).fill(0));

  for (let i = 1; i <= text1.length; i++) {
    for (let j = 1; j <= text2.length; 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];
}

同时可以看出 dp[i][j] 应当只与 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 有关。因此也可以通过只三个变量加上一行的一维数组存储，从而节省空间复杂度。就不在此多说了。