· By John Kavanagh

Edit Distance in TypeScript: Making Each Operation Count

A vintage typewriter with a red ink ribbon and a short line of text on white paper.
Image by Glenn Carstens-Peters, licensed from Unsplash.

Changing one word into another sounds like a small editing job until you try to choose the cheapest sequence of edits. Replace the first mismatch, and you might pay for several replacements where one deletion would have lined everything up. Greedy editing has the confidence of autocorrect, with much the same capacity for making things worse.

For LeetCode's Edit Distance problem, an insertion, deletion, or replacement costs one. We need the minimum total cost. I find this much easier to derive from two prefixes than from a picture of a word being repeatedly rewritten. The prefixes give us a stable question, even as the possible edit sequences branch.

My Longest Common Subsequence article uses a similar table. There, the cells count characters we can keep in order. Here, they count the cheapest edits. The shape is familiar; the meaning of each cell is doing different work.


Give Each Cell a Complete Question

Let cost[i][j] mean the minimum number of edits needed to turn the first i characters of word1 into the first j characters of word2. Those are lengths, not character indexes. The last characters of those prefixes are therefore word1[i - 1] and word2[j - 1].

The empty prefixes belong in the table. Turning an empty string into a prefix of length j requires j insertions. Turning a prefix of length i into an empty string requires i deletions. That gives the first row and column their values without any guesswork.

For cat and cut, the completed table looks like this:

Source prefixEmptyccucut
Empty0123
c1012
ca2112
cat3221

The bottom‑right value is one: replace a with u. But each earlier cell answers its own smaller editing question. For example, converting ca to c costs one deletion, regardless of how we eventually handle the final t.


Work Backwards from the Last Operation

If the final characters match, we can keep them and use the answer for the two shorter prefixes. That is the diagonal cell, cost[i - 1][j - 1]. Keeping a matching pair costs nothing.

If they differ, consider the final edit in an optimal alignment:

  • Delete the last source character. First convert the shorter source prefix to the whole target prefix, then pay one: cost[i - 1][j] + 1.
  • Insert the last target character. First produce the shorter target prefix from the whole source prefix, then pay one: cost[i][j - 1] + 1.
  • Replace the last source character with the last target character. Convert both shorter prefixes, then pay one: cost[i - 1][j - 1] + 1.

We take the minimum of those three costs. Every possible final edit belongs to one of those cases, and each preceding subproblem already has its minimum answer. That combination of complete choices and solved smaller questions is what makes the recurrence useful.

The familiar matching‑character shortcut is safe for unit‑cost edit distance: there is an optimal alignment that keeps equal final characters together. If you introduce unusual operation weights, transpositions, or context‑dependent edits, revisit the recurrence rather than assuming this code still describes your problem.


Keep the Full Table First

I prefer to implement the table before compressing it. It lets me inspect an unexpected answer at the cell where it first goes wrong.

const minDistance = (word1: string, word2: string): number => {
  const rows = word1.length;
  const columns = word2.length;
  const cost = Array.from({ length: rows + 1 }, () =>
    Array<number>(columns + 1).fill(0),
  );

  for (let row = 0; row <= rows; row += 1) cost[row][0] = row;
  for (let column = 0; column <= columns; column += 1) cost[0][column] = column;

  for (let row = 1; row <= rows; row += 1) {
    for (let column = 1; column <= columns; column += 1) {
      cost[row][column] = word1[row - 1] === word2[column - 1]
        ? cost[row - 1][column - 1]
        : 1 + Math.min(
          cost[row - 1][column],
          cost[row][column - 1],
          cost[row - 1][column - 1],
        );
    }
  }

  return cost[rows][columns];
};

Array.from creates a separate array for every row. Filling the outer array with one shared inner array would make a write to one row change all the others. That is an array‑allocation bug wearing an algorithm costume.

The loops run from shorter prefixes to longer ones. The row above is complete, and the cell to the left has already been calculated. Neither input string is modified.

If the string lengths are m and n, the implementation uses O((m + 1)(n + 1)) time and space, including allocation and initialisation. For non‑empty strings, this is the usual O(mn) shorthand. The longer expression also describes the valid empty‑string cases, where we still initialise a row or column.


Reduce Storage Without Losing Yesterday's Values

A cell needs only the value above, the value to its left, and the old diagonal. We can keep one row if we save the old value before overwriting it. I use the shorter string for the columns to minimise storage. Swapping the inputs is valid because insertion and deletion have the same cost here.

const minDistance = (word1: string, word2: string): number => {
  const [longer, shorter] = word1.length >= word2.length
    ? [word1, word2]
    : [word2, word1];
  const cost = Array.from({ length: shorter.length + 1 }, (_, index) => index);

  for (let row = 1; row <= longer.length; row += 1) {
    let diagonal = cost[0];
    cost[0] = row;

    for (let column = 1; column <= shorter.length; column += 1) {
      const above = cost[column];
      cost[column] = longer[row - 1] === shorter[column - 1]
        ? diagonal
        : 1 + Math.min(above, cost[column - 1], diagonal);
      diagonal = above;
    }
  }

  return cost[shorter.length];
};

At the start of an inner‑loop iteration, cost[column] still belongs to the previous row. cost[column - 1] already belongs to the current row. diagonal holds the previous row's value from the preceding column.

After calculating the new cell, we move the saved above value into diagonal. Doing that before saving above would quietly substitute a new value for an old one. The variable names help, but the timing is the essential part.

This version keeps O(min(m, n) + 1) numeric cells and retains the same time complexity. It returns the distance, not the edit sequence. If I needed to show someone exactly which operations to apply, I would usually retain the table and walk backwards through the chosen predecessors. When several paths tie, the application also needs a consistent rule for choosing between equally cheap explanations.


Test the Operations Separately

A matching‑word test is useful, but it never exercises the difficult branch. I want empty strings, a single replacement, an insertion, a deletion, repeated characters, and a case where shifting the alignment beats replacing every mismatch.

For example, abc to bca costs two: delete the first a, then insert it at the end. Three position‑by‑position replacements are valid, but unnecessarily expensive. ab to ba also costs two because swapping adjacent characters is not one of the permitted operations.

My Dynamic Programming Comparison Lab includes both implementations and an independent shortest‑edit search over small inputs. It also checks symmetry, known maximum‑size cases, and agreement between the table and rolling versions. The exhaustive part is deliberately bounded; testing a small alphabet thoroughly is evidence about those inputs, not a proof about all strings.

The challenge restricts inputs to lowercase English letters. JavaScript indexes strings by UTF-16 code unit, which suits that domain. A user‑facing spelling tool would need an explicit decision about Unicode normalisation and whether edits apply to code points or grapheme clusters. A distance alone also says nothing about whether a suggestion makes sense in context.


Wrapping Up

The useful habit here is to describe the prefixes before writing the minimum. Once cost[i][j] has a precise meaning, insertion, deletion, replacement, and the empty‑string cases all have somewhere obvious to go.

Storage compression comes afterwards. Keep the old diagonal safe, keep the left value current, and leave enough of the table around to explain the result when the application needs more than a number.

Downloadable Resource

  • Dynamic Programming Comparison Lab

    Run my fourteen TypeScript solutions across seven problems, with independent checks for string edits, decoding counts, staircase routes, prefixes, and subsequences.

    Download ZIP

Looking for technical direction?

I support teams that need senior judgement on React, Next.js, headless CMS architecture, performance, migrations, and technical SEO.