Edit Distance (Levenshtein)

Minimum insertions, deletions, and substitutions to transform one string to another.

How it works

Edit Distance, also called Levenshtein Distance, measures how dissimilar two strings are by counting the fewest single-character operations required to transform one into the other.

Three operations are allowed, each costing 1: - Insert a character - Delete a character - Replace a character with a different one

The algorithm builds an (m+1) × (n+1) table where dp[i][j] stores the minimum edit cost to transform s1[0..i-1] into s2[0..j-1].

Recurrence: - If s1[i-1] === s2[j-1]: dp[i][j] = dp[i-1][j-1] (characters match — no cost) - Otherwise: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) - dp[i-1][j-1] = replace s1[i-1] with s2[j-1] - dp[i-1][j] = delete s1[i-1] - dp[i][j-1] = insert s2[j-1]

Base cases: dp[0][j] = j (insert j chars), dp[i][0] = i (delete i chars).

The answer is dp[m][n]. Edit distance is a true metric: it satisfies non-negativity, identity, symmetry, and the triangle inequality.

Complexity

Best case

O(mn)

Average case

O(mn)

Worst case

O(mn)

Space

O(mn)

Visualizer

Generating steps…

Where it's used in the real world

Spell checkers in word processors and IDEs

Suggesting the nearest correctly-spelled word for a typo

When a word is not found in the dictionary, spell checkers compute Levenshtein distance from the unknown word to every dictionary candidate and rank suggestions by ascending distance. A threshold of 1–2 edits covers the vast majority of common typing mistakes with minimal false positives.

Version control — git merge conflict resolution

Three-way merging of text files modified by two branches

Git's merge machinery uses edit-distance-based diffing to identify the minimal set of changes each branch made relative to the common ancestor. This lets it automatically merge non-overlapping edits and detect the exact lines in conflict when both branches modified the same region.

Bioinformatics — DNA mutation analysis

Quantifying the mutational distance between genetic sequences

Edit distance over DNA/RNA strings (where insertions, deletions, and substitutions map to biological mutations) is used to measure sequence divergence, infer evolutionary relationships, and detect functionally significant mutations. It underlies global alignment algorithms like Needleman-Wunsch when all operation costs are equal.

Implementation

function editDistance(s1: string, s2: string): number {
  const m = s1.length;
  const n = s2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1], // replace
          dp[i - 1][j],     // delete
          dp[i][j - 1]      // insert
        );
      }
    }
  }

  return dp[m][n];
}

// Usage
console.log(editDistance("kitten", "sitting")); // 3

Related algorithms

Longest Common SubsequenceLive

Find the longest subsequence present in both sequences.

O(mn)

KMP String SearchLive

Find pattern in text in O(n+m) using a failure function.

O(n+m)