在 JavaScript 中查找两个数组中的公共序列

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/2/21 23:08:17

我们需要编写一个 JavaScript 函数，该函数接受两个文字数组，我们将它们称为 arr1 和 arr2。

该函数应查找数组中最长的文字公共序列。该函数最终应返回这些文字的数组。

例如 −

如果输入数组为 −

const arr1 = ['a', 'b', 'c', 'd', 'e'];
const arr2 = ['k', 'j', 'b', 'c', 'd', 'w'];

则输出数组应为 −

const output = ['b', 'c', 'd'];

示例

以下是代码 −

const arr1 = ['a', 'b', 'c', 'd', 'e'];
const arr2 = ['k', 'j', 'b', 'c', 'd', 'w'];
const longestCommonSubsequence = (arr1 = [], arr2 = []) => {
   let str1 = arr1.join('');
   let str2 = arr2.join('');
   const arr = Array(str2.length + 1).fill(null).map(() => Array(str1.length + 1).fill(null));
   for (let j = 0; j <= str1.length; j += 1) {
      arr[0][j] = 0;
   }
   for (let i = 0; i <= str2.length; i += 1) {
      arr[i][0] = 0;
   }
   for (let i = 1; i <= str2.length; i += 1) {
      for (let j = 1; j <= str1.length; j += 1) {
         if (str1[j - 1] === str2[i - 1]) {
            arr[i][j] = arr[i - 1][j - 1] + 1;
         } else {
            arr[i][j] = Math.max(
               arr[i - 1][j],
               arr[i][j - 1],
            );
         }
      }
   }
   if (!arr[str2.length][str1.length]) {
      return [''];
   }
   const res = [];
   let j = str1.length;
   let i = str2.length;
   while (j > 0 || i > 0) {
      if (str1[j - 1] === str2[i - 1]) {
         res.unshift(str1[j - 1]);
         j -= 1;
         i -= 1;
      }
      else if (arr[i][j] === arr[i][j - 1]) {
         j -= 1;
      }
      else {
         i -= 1;
      }
   }
   return res;
};
console.log(longestCommonSubsequence(arr1, arr2));