Tìm chuỗi con chung dài nhất (common streak) trong hai mảng JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào hai mảng các giá trị chữ nghĩa, gọi chúng là arr1 và arr2.

Hàm nên tìm chuỗi con chung dài nhất (longest common streak) của các giá trị trong các mảng. Hàm cuối cùng nên trả về một mảng các giá trị đó.

Ví dụ:

Nếu mảng đầu vào là:

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

Thì mảng đầu ra nên là:

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

Ví dụ

Dưới đây là mã nguồn:

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));

Kết quả

Đầu ra trên console:

['b', 'c', 'd']

Lưu ý: Tên hàm longestCommonSubsequence hơi gây nhầm lẫn vì thuật toán này tìm chuỗi con chung liên tiếp (Longest Common Substring), không phải dãy con chung (Subsequence - có thể không liên tiếp). Code thực hiện đúng cho substring.