Longest Common Subsequence (LCS)

/**
 * @file Longest Common Subsequence (LCS)
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 * _Introduction to Algorithms_. (2nd ed). The MIT Press.
 */

/**
 * Computes the longest common subsequence (LCS) length and the optimal path
 * matrix between two sequences. This function uses dynamic programming to build
 * a table that stores the lengths of LCSs for different segments of the two
 * input arrays.
 *
 * @template T - The type of elements in the input arrays.
 * @param arrayX - The first sequence of elements.
 * @param arrayY - The second sequence of elements.
 * @returns A tuple containing two matrices:
 *
 *   - `computed`: A matrix of LCS lengths for subarrays at the coordinate.
 *   - `trace`: A matrix of directions to trace back the LCS.
 */
function lcsLength<T>(
  arrayX: T[],
  arrayY: T[],
): [computed: number[][], trace: string[][]] {
  const lengthX = arrayX.length;
  const lengthY = arrayY.length;

const computed: number[][] = [];
  const trace: string[][] = [];

for (let i = 0; i <= lengthX; i++) {
    computed[i] = Array.from({length: lengthY + 1}, () => 0);
    trace[i] = Array.from({length: lengthY + 1}, () => '');
  }

for (let i = 1; i <= lengthX; i++) {
    for (let index = 1; index <= lengthY; index++) {
      if (arrayX[i - 1] === arrayY[index - 1]) {
        computed[i][index] = computed[i - 1][index - 1] + 1;
        trace[i][index] = '↖';
      } else if (computed[i - 1][index] >= computed[i][index - 1]) {
        computed[i][index] = computed[i - 1][index];
        trace[i][index] = '↑';
      } else {
        computed[i][index] = computed[i][index - 1];
        trace[i][index] = '←';
      }
    }
  }

return [computed, trace];
}

/**
 * Recursively reconstructs the longest common subsequence (LCS) from the trace
 * matrix generated by the `lcsLength` function. This function traces the
 * optimal path from the bottom-right corner of the matrix to the top-left,
 * building the LCS string by following the directions stored in the matrix.
 *
 * @template T - The type of elements in the input array.
 * @param trace - The matrix containing the optimal path directions.
 * @param arrayX - The sequence of elements used to generate the trace matrix.
 * @param i - The current row index in the `trace` matrix to be considered.
 * @param j - The current column index in the `trace` matrix to be considered.
 * @returns The longest common subsequence as a string.
 */
function printLcs<T>(
  trace: string[][],
  arrayX: T[],
  i: number,
  index: number,
): string {
  if (i === 0 || index === 0) {
    // Return empty when we reach the edge of the table.
    return '';
  }

if (trace[i][index] === '↖') {
    // Include this character and continue recursion
    return printLcs(trace, arrayX, i - 1, index - 1) + arrayX[i - 1];
  }

if (trace[i][index] === '↑') {
    // Recurse upwards
    return printLcs(trace, arrayX, i - 1, index);
  }

// Recurse leftwards
  return printLcs(trace, arrayX, i, index - 1);
}

(() => {
  const arrayX = 'ABCBDAB'.split('');
  const arrayY = 'BDCABA'.split('');
  const [_computed, trace] = lcsLength<string>(arrayX, arrayY);

const result = printLcs<string>(trace, arrayX, arrayX.length, arrayY.length);
  if (result !== 'BCBA' && result !== 'BDAB') {
    console.log('Did not find expected result');
  }

console.log(`Longest common subsequence: ${result}`);
})();