【JavaScript 算法】最长公共子序列：字符串问题的经典解法

最长公共子序列（Longest Common Subsequence，LCS）是字符串处理中的经典问题。给定两个字符串，找出它们的最长公共子序列，即在不改变字符顺序的情况下，从这两个字符串中抽取的最长的子序列。本文将详细介绍最长公共子序列的原理、实现及其应用。

一、算法原理

最长公共子序列问题可以通过动态规划（Dynamic Programming）来解决。其基本思想是构建一个二维数组 dp，其中 dp[i][j] 表示字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符的最长公共子序列的长度。

状态转移方程

1. 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
2. 如果 text1[i-1] != text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

初始条件

1. 当 i == 0 或 j == 0 时，dp[i][j] = 0，因为空字符串与任何字符串的公共子序列长度为0。

二、算法实现

Longest Common Subsequence Flowchart

以下是最长公共子序列的JavaScript实现：

/**
 * 动态规划实现最长公共子序列
 * @param {string} text1 - 第一个字符串
 * @param {string} text2 - 第二个字符串
 * @return {number} - 最长公共子序列的长度
 */
function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); // 初始化 dp 数组

  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][n]; // 返回最长公共子序列的长度
}

// 示例
const text1 = "abcde";
const text2 = "ace";
console.log(longestCommonSubsequence(text1, text2)); // 输出: 3

注释说明：

1. 初始化dp数组：
   • const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));：创建一个二维数组，大小为 (m+1) x (n+1)，并初始化为0。
2. 遍历字符串：
   • for (let i = 1; i <= m; i++)：遍历字符串 text1 的每个字符。
   • for (let j = 1; j <= n; j++)：遍历字符串 text2 的每个字符。
3. 状态转移方程：
   • 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]);：如果当前字符不同，则 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。
4. 返回结果：
   • return dp[m][n];：返回 dp 数组的最后一个元素，即最长公共子序列的长度。

三、应用场景

1. 文本比较：在文本编辑器中比较两个文档的差异。
2. 版本控制：在版本控制系统中比较两个版本的代码差异。
3. 基因序列分析：在生物信息学中比较DNA序列的相似性。
4. 数据比较：在数据分析中比较两个数据集的相似性。

四、总结

最长公共子序列是字符串处理中的经典问题，通过动态规划的方法，可以高效地解决这个问题。理解和掌握最长公共子序列的算法，可以应用于文本比较、版本控制、基因序列分析和数据比较等领域。