javascript 实现最长公共子序列算法（附带原理思路讲解）

站长

2023年11月24日 12:43 · 阅读数 8

建议阅读时间：12 分钟

前言

本文适用于经常使用 js 刷算法的前端同学

正文

最长公共子序列是一个经典的算法，并且这个算法在实际开发中也经常会大放光彩

问题描述

题意如下：详见 LCR 095. 最长公共子序列

给定两个字符串str1和str2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回0。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

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

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

思路

这个问题其实并不难，我们可以想象这样一种情况 javascript 实现最长公共子序列算法（附带原理思路讲解）当字符串 str1 中某个字符 X 与字符串 str2 中某个字符相同时那么图中的字符串 C 与字符串 D 的最长公共子序列是不是就是字符串 A 与字符串 B 的最长公共子序列加上字符 X

那么如果 str1 中某个字符 X 与字符串 str2 中某个字符不同的时候 javascript 实现最长公共子序列算法（附带原理思路讲解）图中字符串 C 与字符串 D 的最长公共子序列就可能与字符串 C 与 B 的最长公共子序列 S1 相同，也可能与字符串 A 与 D 的最长公共子序列 S2 相同 那么看这两个最长公共子序列 S1 与 S2 哪个长，哪个长字符串 C 与字符串 D 的最长公共子序列就用哪个

应该不难理解，我们用符号来表达一下记字符 str[k] 为字符串 str 中第 k 位的字符(k 从 1 开始数) 记字符串 str(x) 为由字符串 str1 中前 x 位组成的字符串记字符串 S(i, j) 为字符串 str1(i)与字符串 str(j)的最长公共子序列记 L(i, j) 为字符串 S(i, j) 的长度

如果字符 str1[i]与字符 str2[j]相同
- 那么 S(i, j) = S(i - 1, j - 1) + str1[i]，L(i, j) = L(i - 1, j - 1) + 1
如果字符 str1[i]与字符 str2[j]不同
- 那么如果 L(i - 1, j) > L(i, j - 1)
  - 则 S(i, j) = S(i - 1, j)，L(i, j) = L(i - 1, j)
- 如果 L(i - 1, j) <= L(i, j - 1) (等于放到上面也可以，无所谓)
  - 则 S(i, j) = S(i, j - 1)，L(i, j) = L(i, j - 1)

题目只想求最长公共子序列的长度，那我们就只需要计算维护 L(i, j) 即可

通过这种策略，我们可以先求出 L(1, 1) L(1, 2)…… L(1, n)，再求出 L(2, 1) L(2, 2) …… L(2, n)，最终求出 L(m, 1) L(m, 2) …… L(m, n) 这个 L(m, n) 就是我们想要的最终结果(m 为 str1 的长度, n 为 str2 的长度)

S(0, j) 代表由字符串 str1 前 0 位组成的字符串(即空字符串)与字符串str2(j)的最长公共子序列，因为前者为空字符串，所以最长公共子序列也为空字符串，故 S(0, j) 为空字符串，L(0, j) = 0，同理 L(i, 0) = 0

理论有了，我们开始写代码

function longestCommonSubsequence(str1, str2) {
  let m = str1.length;
  let n = str2.length;

  // 初始化二维数组 l，l[i][j] 代表上述 L(i, j)
  let l = new Array(m + 1);
  for (let i = 0; i < m + 1; i++) {
    l[i] = new Array(n + 1);
  }

  // 将 L(i, 0) 与 L(0, j) 赋值为 0
  for (let i = 0; i < m + 1; i++) {
    l[i][0] = 0;
  }
  for (let i = 0; i < n + 1; i++) {
    l[0][i] = 0;
  }

  // 按照上文策略执行
  for (let i = 1; i < m + 1; i++) {
    for (let j = 1; j < n + 1; j++) {
      // -1 是因为代码中字符串是从 0 开始数
      // str1[i - 1] 代表字符串 str1 中第 i 个字符
      // 例如第 1 个字符是 str[0]，第 2 个字符是 str[1]
      if (str1[i - 1] === str2[j - 1]) {
        l[i][j] = l[i - 1][j - 1] + 1;
      } else {
        if (l[i - 1][j] > l[i][j - 1]) {
          l[i][j] = l[i - 1][j];
        } else {
          l[i][j] = l[i][j - 1];
        }
      }
    }
  }
  return l[m][n];
}

这样我们就解决了求两个字符串最长公共子序列长度的问题那如果我们想要求出这个最长公共子序列的本体是什么要怎么做呢

求最长公共子序列本体（非长度）

有一种方法，可以这样我们在维护 L(i, j) 的时候同时维护 S(i, j) 这样最后的 S(m, n) 就是我们要的 str1 与 str2 的最长公共子序列实践开始

function longestCommonSubsequence(str1, str2) {
  let m = str1.length;
  let n = str2.length;

  // 初始化二维数组 l，l[i][j] 代表上述 L(i, j)
  let l = new Array(m + 1);
  for (let i = 0; i < m + 1; i++) {
    l[i] = new Array(n + 1);
  }

  // 初始化二维数组 s，s[i][j] 代表上述 S(i, j)
  let s = new Array(m + 1);
  for (let i = 0; i < m + 1; i++) {
    s[i] = new Array(n + 1);
  }

  // 将 L(i, 0) 与 L(0, j) 赋值为 0
  for (let i = 0; i < m + 1; i++) {
    l[i][0] = 0;
  }
  for (let i = 0; i < n + 1; i++) {
    l[0][i] = 0;
  }

  // 将 S(i, 0) 与 S(0, j) 赋值为空字符串
  for (let i = 0; i < m + 1; i++) {
    s[i][0] = "";
  }
  for (let i = 0; i < n + 1; i++) {
    s[0][i] = "";
  }

  // 按照上文策略执行
  for (let i = 1; i < m + 1; i++) {
    for (let j = 1; j < n + 1; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        l[i][j] = l[i - 1][j - 1] + 1;
        s[i][j] = s[i - 1][j - 1] + str1[i - 1];
      } else {
        if (l[i - 1][j] > l[i][j - 1]) {
          l[i][j] = l[i - 1][j];
          s[i][j] = s[i - 1][j];
        } else {
          l[i][j] = l[i][j - 1];
          s[i][j] = s[i][j - 1];
        }
      }
    }
  }
  return s[m][n];
}

显然这种方式是可行的，不过不难发现，我们中间存储了不少字符串，这会导致空间复杂度很高我们最好不使用这种方式那还能怎么操作呢我们可以反其道而行之

如果 L(i, j) = L(i - 1, j - 1) + 1
- 那么说明 S(i, j) = S(i - 1, j - 1) + str1[i]
- 也就是说 str1[i] 是 S(i, j) 的最后一个字符
如果 L(i, j) != L(i - 1, j - 1)
- 那么 L(i, j) 一定是通过 L(i - 1, j) 或者 L(i, j - 1) 来的
- 也就是说 L(i, j) 和二者哪个相同，就是通过哪个得到的，都相同就无所谓了，随便选一个即可

那么只要我们从 L(i, j) 开始，一点一点向上找，就能将每个字符都找出来，最终这些字符组成的字符串就是 S(i, j) 如图所示： javascript 实现最长公共子序列算法（附带原理思路讲解）理论有了，开始实践：

function longestCommonSubsequence(str1, str2) {
  let m = str1.length;
  let n = str2.length;

  // 初始化二维数组 l，l[i][j] 代表上述 L(i, j)
  let l = new Array(m + 1);
  for (let i = 0; i < m + 1; i++) {
    l[i] = new Array(n + 1);
  }

  // 将 L(i, 0) 与 L(0, j) 赋值为 0
  for (let i = 0; i < m + 1; i++) {
    l[i][0] = 0;
  }
  for (let i = 0; i < n + 1; i++) {
    l[0][i] = 0;
  }

  // 按照上文策略执行
  for (let i = 1; i < m + 1; i++) {
    for (let j = 1; j < n + 1; j++) {
      // -1 是因为代码中字符串是从 0 开始数
      // str1[i - 1] 代表字符串 str1 中第 i 个字符
      // 例如第 1 个字符是 str[0]，第 2 个字符是 str[1]
      if (str1[i - 1] === str2[j - 1]) {
        l[i][j] = l[i - 1][j - 1] + 1;
      } else {
        if (l[i - 1][j] > l[i][j - 1]) {
          l[i][j] = l[i - 1][j];
        } else {
          l[i][j] = l[i][j - 1];
        }
      }
    }
  }

  // 初始坐标为 (m, n)
  let x = m;
  let y = n;
  let res = []; // 用来保存每个字符
  // 如果有 x 和 y 都不为 0 则一直循环找
  while (x !== 0 && y !== 0) {
    // 如果 L(i, j) = L(i - 1, j - 1) + 1，则保存字符 str1[i]
    if (l[x][y] === l[x - 1][y - 1] + 1) {
      res.push(str1[x - 1]);

      // 向左上角走
      x--;
      y--;
    } else {
      // 不相同的话看是从那边来的就走到那边
      if (l[x][y] === l[x - 1][y]) {
        x--;
      } else {
        y--;
      }
    }
  }

  // 由于 res 是倒着存进来的，所以最后返回结果的时候反转一下
  return res.reverse().join("");
}

通过这种方式，我们就先以 O(m * n) 的时间负责度先找到了最长公共子序列的长度，然后以 O(m + n) 的时间复杂度找到了这个最长公共子序列中的每个字符，最终得出最长公共子序列

你学会了吗，学会了就试着自己独立写一遍吧！

具体这个最长公共子序列算法可以用在什么地方，我之后会发几个使用这个算法具体场景的例子，敬请期待！

结语

希望这篇文章对你能够有所帮助，感谢你的喜欢