หา Common Streak (Longest Common Subsequence) ระหว่างสองอาร์เรย์ใน JavaScript

Longest Common Subsequence (LCS)

หาลำดับย่อย (Subsequence) ที่ยาวที่สุดที่ปรากฏในทั้งสองอาร์เรย์ ไม่จำเป็นต้องติดกัน (ต่างจาก Substring)

ตัวอย่าง

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

LCS = ['b', 'c', 'd'] (ความยาว 3)

โค้ดตัวอย่าง (Dynamic Programming)

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('');
  
  // DP Table: (str2.length+1) x (str1.length+1)
  const arr = Array(str2.length + 1).fill(null).map(() => 
    Array(str1.length + 1).fill(null));
  
  // Initialize
  for (let j = 0; j <= str1.length; j++) arr[0][j] = 0;
  for (let i = 0; i <= str2.length; i++) arr[i][0] = 0;
  
  // Fill DP table
  for (let i = 1; i <= str2.length; i++) {
    for (let j = 1; j <= str1.length; j++) {
      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]);
      }
    }
  }
  
  // Backtrack หา sequence จริง
  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--; i--;
    } else if (arr[i][j] === arr[i][j - 1]) {
      j--;
    } else {
      i--;
    }
  }
  return res;
};

console.log(longestCommonSubsequence(arr1, arr2));

ผลลัพธ์

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

ความซับซ้อน

• Time: O(m × n)
• Space: O(m × n) สามารถลดเหลือ O(min(m,n)) ได้

โค้ดเวอร์ชัน Generic (รองรับ Array ตรงๆ)

const lcsArray = (arr1, arr2) => {
  const m = arr1.length, n = arr2.length;
  const dp = Array(n + 1).fill(0).map(() => Array(m + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (arr2[i-1] === arr1[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]);
    }
  }
  
  // Reconstruct
  const result = [];
  let i = n, j = m;
  while (i > 0 && j > 0) {
    if (arr2[i-1] === arr1[j-1]) {
      result.unshift(arr2[i-1]);
      i--; j--;
    } else if (dp[i-1][j] > dp[i][j-1]) i--;
    else j--;
  }
  return result;
};

ความแตกต่าง LCS vs Longest Common Substring