介绍

最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较（英语：data comparison）程序，比如 Diff 工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如 Git 用来调和文件之间的改变。

最长公共子串：在计算机科学中，最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。

定义：一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

实现

JavaScript

/*
Problem:
Given two sequences, find the length of longest subsequence present in both of them.
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”

Our Solution:
We use recursion with tabular memoization.
Time complexity: O(M x N)
Solving each subproblem has a cost of O(1). Again, there are MxN subproblems,
and so we get a total time complexity of O(MxN).
Space complexity: O(M x N)
We need to store the answer for each of the MxN subproblems.

Improvement:
It's possible to optimize space complexity to O(min(M, N)) or time to O((N + r)log(N))
where r is the number of matches between the two sequences. Try to figure out how.

References:
[wikipedia](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem)
[leetcode](https://leetcode.com/problems/longest-common-subsequence/)
*/

/**
 * Finds length of the longest common subsequence among the two input string
 * @param {string} str1 Input string #1
 * @param {string} str2 Input string #2
 * @returns {number} Length of the longest common subsequence
 */
function longestCommonSubsequence (str1, str2) {
  const memo = new Array(str1.length + 1).fill(null).map(() => new Array(str2.length + 1).fill(null))

  function recursive (end1, end2) {
    if (end1 === -1 || end2 === -1) return 0
    if (memo[end1][end2] !== null) return memo[end1][end2]

    if (str1[end1] === str2[end2]) return memo[end1][end2] = 1 + recursive(end1 - 1, end2 - 1)
    return memo[end1][end2] = Math.max(recursive(end1 - 1, end2), recursive(end1, end2 - 1))
  }

  return recursive(str1.length - 1, str2.length - 1)
}

参考

• Longest common subsequence problem - Wikiwand (opens new window)
• 最长公共子序列 - Wikiwand (opens new window)