Levenshtein Distance Visualizer

Enter two strings to see their Levenshtein (edit) distance — the minimum number of single-character edits needed to transform one into the other.

Worked example — Levenshtein Distance Visualizer

Edit distance	3
Similarity	57.14%

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Levenshtein Distance Visualizer

The Levenshtein distance between two strings is the smallest number of single-character edits that turns one into the other, where an edit is an insertion, a deletion, or a substitution. It is a minimum over every possible way of doing the job, which is what makes it hard to compute by eye and easy to compute with a grid: there are astronomically many edit sequences, and this counts the shortest without listing any of them.

What each symbol means

m, n: the lengths of the two strings, A and B.
D(i, j): the cheapest way to turn the first i characters of A into the first j characters of B. One cell of the table on this page.
[aᵢ ≠ bⱼ]: costs 1 when those two characters differ and 0 when they match — the substitution price, which is free if there is nothing to substitute.
d: the answer, D(m, n): the bottom-right cell.

Where the formula comes from

Decide what one cell means before filling any of them. Let D(i, j) be the fewest edits that turn A’s first i characters into B’s first j. The number you want is D(m, n), and every other cell is a smaller version of the same question.
The edges need no thinking. To build B’s first j characters starting from nothing you must insert all j of them, so D(0, j) = j. To reduce A’s first i characters to nothing you must delete all i, so D(i, 0) = i. That is the top row and the left column of the grid, and it is why they simply count upwards.
Now the step that does all the work. Take any optimal script for D(i, j) and look only at its last move. There are three possibilities and no others: it deleted aᵢ, leaving the job D(i−1, j); it inserted bⱼ, leaving D(i, j−1); or it paired aᵢ with bⱼ, leaving D(i−1, j−1). Each of those is a cell you have already filled.
So the cell is the cheapest of the three: D(i, j) = min( D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [aᵢ ≠ bⱼ] ). Fill the grid left to right and top to bottom, and when you reach any cell its three neighbours are already known. That is the whole algorithm — m × n cells, three comparisons each.

How to read what you see

The grid on this page is that table. Rows are A, columns are B, and the extra row and column at the top-left are the empty prefixes from step 2 — which is why they count 0, 1, 2, 3. Cell shading is the value: the pale diagonal corridor is where the two strings still agree cheaply. Hover or tap any cell and the panel underneath spells out step 3 for that cell — the three candidates, each with its arithmetic, and the winner highlighted. The coloured line is one optimal route traced back from the bottom-right corner, and the alignment strip below it is that same route written out as characters.

Assumes: Every edit costs exactly 1, and characters are compared for exact equality — no case folding, no Unicode normalisation, and no notion of which characters look or sound alike. Two consequences are visible here. What gets counted here is UTF-16 code units, not what you would call letters: type a single emoji into one box and the table is 3 × 1, because one emoji is two units, and deleting it costs 2. And café typed with a precomposed é against café typed as e plus a combining accent reads distance 2 while the two look identical on screen.
Breaks when: The grid is m × n cells, so the work grows as the product of the lengths. That is fine for two words and hopeless for a query against a million-entry dictionary, which is a million grids. The natural response is to look for a cleverer algorithm, and the surprise is that essentially none exists: Backurs and Indyk showed in 2015 that a strongly subquadratic edit distance would refute the Strong Exponential Time Hypothesis. Real spell-checkers do not beat the bound, they avoid it — cutting off once the distance exceeds a small limit, or indexing so that almost every candidate is never compared at all.

The grid is small because every sub-question is only asked once 🖖

Searching through possible sequences of edits is hopeless — the number of orderings explodes with the length of the words. The insight that rescues it is that any pair of prefixes has exactly one best answer, and that answer never changes no matter what happens later in the string. So rather than explore sequences, you fill a grid: one row per letter of the first word, one column per letter of the second, plus an empty row and column standing for the empty prefix. Turning kitten into sitting is therefore 7 × 8 = 56 cells, each one decided by glancing at three already-filled neighbours, and the answer 3 is waiting in the bottom-right corner. The work grows with the product of the two lengths, not with the number of ways to edit.

A swap costs two edits until you say otherwise 🖖

Type form and from and Levenshtein answers 2. It has no notion that the letters were swapped, so it pays for two substitutions. But transposed letters are among the most common typing errors there are, which is why Damerau added a fourth move: if the two characters you need are the two you have in the other order, take them both for the price of one. Switch the cost model above and the same pair costs 1. Nothing about the words changed — the price list did. That is worth remembering wherever an edit distance is used as a similarity score, because the number is a property of the cost model you picked as much as of the two strings.

The fast version cannot draw this picture 🖖

Every cell needs only the row above it and the cell to its left, so the rows further back earn nothing by staying. Real implementations take that deal and keep two rows instead of the whole table, which turns the memory from m × n into min(m, n) — for two strings of a thousand characters, about a million cells down to two thousand. What they give up is exactly what is drawn above. The distance survives in the final cell, but the route to it lived in the rows that were overwritten, so a two-row implementation can tell you two strings are three edits apart and not which three. Recovering the route without the full grid is a harder problem than it looks, and Hirschberg solved it in 1975 by splitting the table down the middle and recursing into both halves.

Problem solved in full

The cheapest edit sequence to turn kitten into sitting 5 steps
Turn kitten into sitting. Find the cheapest edit sequence and prove no cheaper one exists — then work out what this costs when the second word is a whole dictionary.
1. The recurrence is the whole algorithm. Each cell asks what it costs to arrive here by deleting, by inserting, or by lining the two current characters up — the last option free when they agree. A cell needs only the three neighbours above and to its left, so one left-to-right sweep fills the table.
  
  $d_{i, j} = min ⎩ ⎨ ⎧ d_{i - 1, j} + 1 d_{i, j - 1} + 1 d_{i - 1, j - 1} + [a_{i} \neq = b_{j}]$
2. Before filling anything, bracket the answer. The lengths differ by one, so at least one insertion is unavoidable; and rewriting the word outright costs 7. The answer lies between, which already disposes of most guesses.
  
  $∣ a ∣ - ∣ b ∣ = 1 \leq d \leq max (∣ a ∣, ∣ b ∣) = 7$
3. Three edits do it: substitute k → s, substitute e → i, insert g. Each is a single legal edit and the chain ends on the target.
  
  $k \underline{i} tten \to s \underline{i} tten \to sitt \underline{i} n \to sitting$
4. Exhibiting three edits only proves the distance is at most 3. The table proves it is exactly 3, because every route to the bottom-right corner is scored and the minimum is taken at every cell along the way. That is the difference between finding an answer and knowing it cannot be beaten.
  
  $d = 3, similarity = 1 - \frac{3}{7} = 0.5714 = 57.14%$
5. The cost is one cell per pair of characters — 42 here, which is nothing. Against a 100 000-word dictionary at seven letters apiece it is over four million cell updates for a single lookup.
  
  $Θ (∣ a ∣ ∣ b ∣) = 6 \times 7 = 42 cells; d (a, c) \leq d (a, b) + d (b, c)$
Answer

The tool prints 3 and a similarity of 57.14%, which is 1 − 3/7: the distance normalised by the longer word. Both come from a table you can fill by hand in a minute. What does not scale is the table — the work is Θ(mn), so doubling both strings quadruples it, and every spellchecker you have used is built around not doing this. The escape is not a faster table. It is that Levenshtein satisfies the triangle inequality, so d(a, c) ≤ d(a, b) + d(b, c) lets an index prove a candidate is too far away without ever measuring how far.

$d (kitten, sitting) = 3, 1 - \frac{3}{7} = 57.14%$

References (4)

The theory section ends on why nobody has a much faster algorithm. This is the result that says they probably cannot have one: A. Backurs & P. Indyk, "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)." SIAM Journal on Computing 47(3), 1087–1097, 2018; first presented at STOC 2015.
The grid this tool fills, and why filling each cell once is enough: R. A. Wagner & M. J. Fischer, "The String-to-String Correction Problem." Journal of the ACM 21(1), 168–173, 1974 — the dynamic-programming algorithm for the edit distance Levenshtein had defined in 1965.
The fourth move in the Damerau cost model, and the survey of typing errors that argued for it: F. J. Damerau, "A technique for computer detection and correction of spelling errors." Communications of the ACM 7(3), 171–176, 1964.
Insight block 3 ends on the problem of recovering the route without keeping the grid. This is the paper that solved it: D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences." Communications of the ACM 18(6), 341–343, 1975.

By the 42Math team · Updated 2026-05-21

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

kitten → sitting - kitten → sitting is the textbook case, and the answer is 3: two substitutions and one insertion, leaving 57.14% similarity
book → back - book → back is 2 edits between two four-letter words, which the tool reads as 50.00% similar
Saturday → Sunday - Saturday → Sunday takes 3 edits and reads 62.50% similar, two of them deletions
form → from (swap) - form → from is a single swap under Damerau–Levenshtein, which the tool reads as 75.00% similar
DNA mismatch - GATTACA → GCATGCG takes 4 edits and 42.86% — the same measure applied to sequence data