What is edit distance?

Edit distance, or Levenshtein distance, is the minimum number of single-character edits — insertions, deletions or substitutions — needed to change one string into another.

How does the dynamic-programming table work?

A grid of size (m+1)x(n+1) stores the edit distance between every prefix of the two strings. Each cell is the minimum of its left, top and diagonal neighbours plus the cost of the edit, so the bottom-right cell holds the full distance.

Why is the diagonal move special?

A diagonal move aligns one character of each string. If the characters match, the cost is zero (a copy); if they differ, it is a substitution costing one.

What is backtracking in this algorithm?

After filling the table you start at the bottom-right cell and walk back to the top-left, each step choosing the neighbour that produced the current value. This reconstructs the actual sequence of edits.

What is the time complexity?

Filling the table takes O(m*n) time and O(m*n) space, where m and n are the string lengths. Space can be reduced to O(min(m,n)) if only the distance is needed.

Where is edit distance used?

Spell checkers, fuzzy search, DNA and protein alignment, plagiarism detection, OCR correction and diff tools all rely on edit-distance computations.

Is the answer always unique?

The distance value is unique, but there can be several optimal edit paths of the same total cost. The backtracking here picks one consistent path.

What is the difference between Levenshtein and Hamming distance?

Hamming distance only counts substitutions and requires equal-length strings. Levenshtein distance also allows insertions and deletions, so it handles strings of different lengths.

Can the operations have different costs?

Yes. Weighted edit distance assigns different costs to insertion, deletion and substitution, which is common in spell-checking where some mistakes are more likely than others. This simulation uses unit costs.

Why does the path stay near the diagonal for similar words?

When two strings are alike, most characters align directly, so the optimal path runs close to the main diagonal with only a few off-diagonal insertion or deletion steps.

Home▸Algorithms & AI▸Edit Distance — Levenshtein DP Table

📝 Edit Distance — Levenshtein DP Table

Fill the Levenshtein dynamic-programming table cell by cell, then backtrack the cheapest path of insertions, deletions and substitutions that turns one string into another.

Algorithms & AI3DModerate60 FPS

About Edit Distance (Levenshtein)

Edit distance, formalised by Vladimir Levenshtein in 1965, measures the minimum number of single-character insertions, deletions, and substitutions required to transform one string into another. It is computed in O(mn) time and O(mn) space (or O(min(m,n)) space with the row-by-row trick) using dynamic programming: filling an (m+1)×(n+1) table where each cell d[i][j] holds the edit distance between the first i characters of the source and the first j characters of the target. The algorithm is foundational in spell checkers, DNA sequence alignment (where substitutions model mutations), and fuzzy string matching in search engines.

The simulation fills the DP table cell by cell at adjustable speed, colour-coding each operation. Once complete, backtracking highlights the optimal alignment path through the matrix, showing exactly which insertions, deletions, and substitutions were chosen.

Frequently Asked Questions

What is the recurrence relation used to fill the Levenshtein matrix?

Each cell is filled as: d[i][j] = d[i−1][j−1] if s[i] = t[j] (characters match, no cost); otherwise d[i][j] = 1 + min(d[i−1][j], d[i][j−1], d[i−1][j−1]) for deletion, insertion, and substitution respectively. The first row and column are initialised to 0…m and 0…n since transforming an empty string requires i insertions or j deletions.

What is the difference between edit distance and Hamming distance?

Hamming distance counts only substitutions between two strings of equal length. Edit distance is strictly more general: it permits insertions and deletions, making it applicable to strings of different lengths. For equal-length strings with no indels, Hamming and Levenshtein distance agree. Hamming distance is O(n) to compute, while Levenshtein is O(mn), reflecting its greater expressiveness.

How does edit distance relate to the Longest Common Subsequence (LCS)?

If only insertions and deletions are allowed (no substitutions), then edit distance = m + n − 2·LCS(s, t): the two extra characters for every matched pair in the LCS cancel a deletion and an insertion. Levenshtein adds substitutions (cost 1) as a shortcut that replaces a deletion + insertion (cost 2) when beneficial. The DP tables share the same structure, differing only in the substitution cost term.

How does backtracking recover the optimal alignment from the DP table?

Starting at d[m][n], the algorithm moves to whichever predecessor cell (diagonal for match/substitution, left for insertion, up for deletion) has the smallest value. Ties can be broken arbitrarily; each choice yields a different but equally optimal alignment. The sequence of moves read in reverse gives the edit script (CIGAR string in bioinformatics notation).

What is the Damerau–Levenshtein distance?

Damerau–Levenshtein adds transposition of two adjacent characters as a fourth elementary operation at cost 1. This is more appropriate for modelling human typing errors, where transpositions account for up to 80% of misspellings. Computing it requires a more complex DP with O(|Σ|) additional arrays to track the last position each character appeared, giving O(mn) time but with a larger constant.

Can edit distance be computed faster than O(mn)?

For general strings, the best known algorithm runs in O(mn/log n) using word-level parallelism (the Masek–Paterson algorithm and bit-vector variants). For strings that are "almost equal" (distance k ≪ n), an O(kn) algorithm by Ukkonen exists that only fills a diagonal band of width 2k+1 in the matrix. In practice, bit-parallelism variants are used in tools like agrep and the Unix diff utility.

How is edit distance used in bioinformatics?

In sequence alignment, nucleotides A, C, G, T are the alphabet and a substitution matrix (e.g., BLOSUM62 for proteins) replaces the uniform cost-1 penalty. The Smith–Waterman algorithm is a local edit-distance variant that finds the highest-scoring aligned subsequence, revealing conserved functional domains. Global alignment uses the Needleman–Wunsch algorithm, which is mathematically identical to Levenshtein with affine gap penalties.

What is the edit distance between "kitten" and "sitting"?

The edit distance is 3: substitute 'k'→'s' (kitten→sitten), substitute 'e'→'i' (sitten→sittin), and insert 'g' at the end (sittin→sitting). This is the classic textbook example used to illustrate the algorithm, with the 7×8 DP table often shown in algorithm courses.

How do spell checkers use edit distance?

A spell checker computes the edit distance between a misspelled word and every word in a dictionary (or a pruned candidate list from a BK-tree), then suggests words within distance 1 or 2 as corrections. BK-trees exploit the triangle inequality of edit distance to prune the dictionary search, reducing average comparisons from O(|dict|) to O(|dict|^0.2) in practice.

Does edit distance satisfy the triangle inequality?

Yes — edit distance is a proper metric: it is non-negative, symmetric, zero iff the strings are identical, and satisfies d(s, u) ≤ d(s, t) + d(t, u). This metric property enables BK-trees and VP-trees to index strings for fast approximate nearest-neighbour search, which underlies similarity search in spell-correction and DNA databases.

⚙ Under the hood

Fill the Levenshtein dynamic-programming table cell by cell, then backtrack the cheapest path of insertions, deletions and substitutions that turns one string into another.

edit distanceLevenshteindynamic programmingalignmentCanvas 2D

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install