Longest Common Subsequence (LCS) | The Personal Website of Dustin Boston

code.ts

/**
 * @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.
 */
export 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.
 */
export 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}`);
})();

longest_common_subsequence_test.ts

import {assertEquals} from "https://deno.land/std@0.202.0/assert/assert_equals.ts";
import {
  lcsLength,
  printLCS,
} from "../../../../data/algorithms/src/longest_common_subsequence.ts";

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

  // Console.table(computed);
  // console.table(trace);

  const result = printLCS<string>(trace, arrayX, arrayX.length, arrayY.length);
  assertEquals(result, "BCBA"); // OR BDAB
});

test(function numericLCS() {
  const arrayX = "10010101".split("").map(Number);
  const arrayY = "010110110".split("").map(Number);

  const [_computed, trace] = lcsLength<number>(arrayX, arrayY);

  const result = printLCS<number>(trace, arrayX, arrayX.length, arrayY.length);
  assertEquals(result, "100110"); // OR 101010
});