Longest common subsequence problem

/**
 * @param {string[]} set1
 * @param {string[]} set2
 * @return {string[]}
 */
export default function longestCommonSubsequence(set1, set2) {
  // Init LCS matrix.
  const lcsMatrix = Array(set2.length + 1).fill(null).map(() => Array(set1.length + 1).fill(null));

  // Fill first row with zeros.
  for (let columnIndex = 0; columnIndex <= set1.length; columnIndex += 1) {
    lcsMatrix[0][columnIndex] = 0;
  }

  // Fill first column with zeros.
  for (let rowIndex = 0; rowIndex <= set2.length; rowIndex += 1) {
    lcsMatrix[rowIndex][0] = 0;
  }

  // Fill rest of the column that correspond to each of two strings.
  for (let rowIndex = 1; rowIndex <= set2.length; rowIndex += 1) {
    for (let columnIndex = 1; columnIndex <= set1.length; columnIndex += 1) {
      if (set1[columnIndex - 1] === set2[rowIndex - 1]) {
        lcsMatrix[rowIndex][columnIndex] = lcsMatrix[rowIndex - 1][columnIndex - 1] + 1;
      } else {
        lcsMatrix[rowIndex][columnIndex] = Math.max(
          lcsMatrix[rowIndex - 1][columnIndex],
          lcsMatrix[rowIndex][columnIndex - 1],
        );
      }
    }
  }

  // Calculate LCS based on LCS matrix.
  if (!lcsMatrix[set2.length][set1.length]) {
    // If the length of largest common string is zero then return empty string.
    return [''];
  }

  const longestSequence = [];
  let columnIndex = set1.length;
  let rowIndex = set2.length;

  while (columnIndex > 0 || rowIndex > 0) {
    if (set1[columnIndex - 1] === set2[rowIndex - 1]) {
      // Move by diagonal left-top.
      longestSequence.unshift(set1[columnIndex - 1]);
      columnIndex -= 1;
      rowIndex -= 1;
    } else if (lcsMatrix[rowIndex][columnIndex] === lcsMatrix[rowIndex][columnIndex - 1]) {
      // Move left.
      columnIndex -= 1;
    } else {
      // Move up.
      rowIndex -= 1;
    }
  }

  return longestSequence;
}

/* eslint-disable no-param-reassign */
/**
 * Longest Common Subsequence (LCS) (Recursive Approach).
 *
 * @param {string} string1
 * @param {string} string2
 * @return {number}
 */
export default function longestCommonSubsequenceRecursive(string1, string2) {
  /**
   *
   * @param {string} s1
   * @param {string} s2
   * @return {string} - returns the LCS (Longest Common Subsequence)
   */
  const lcs = (s1, s2, memo = {}) => {
    if (!s1 || !s2) return '';

    if (memo[`${s1}:${s2}`]) return memo[`${s1}:${s2}`];

    if (s1[0] === s2[0]) {
      return s1[0] + lcs(s1.substring(1), s2.substring(1), memo);
    }

    const nextLcs1 = lcs(s1.substring(1), s2, memo);
    const nextLcs2 = lcs(s1, s2.substring(1), memo);

    const nextLongest = nextLcs1.length >= nextLcs2.length ? nextLcs1 : nextLcs2;

    memo[`${s1}:${s2}`] = nextLongest;

    return nextLongest;
  };

  return lcs(string1, string2);
}