DYNAMIC PROGRAMMING · CORE

Edit distance

Count the fewest single-character inserts, deletes, and replacements that turn one string into another.

Time O(m × n)Space O(m × n)7 practice problemsStep-through picture

The idea

The edit distance between two strings, also called the Levenshtein distance, is the smallest number of edits that turns the first into the second. One edit is inserting a character, deleting a character, or replacing one character with another. "color" to "colour" is 1 edit: insert u.

The DP table compares prefixes, just like the longest common subsequence. Cell dist[i][j] holds the edit distance between the first i characters of a and the first j characters of b.

It is how spell checkers and "did you mean" messages find the closest known word: compute the distance to each candidate and suggest the smallest.

An everyday example

Fixing a typo with the fewest keystrokes

You typed kitten but meant sitting. Working from the end of both words, each step you choose: if the last letters already match, leave them. If not, either delete the last letter you typed, type the missing letter, or overwrite your letter with the right one. Each fix costs one keystroke, and you want the cheapest sequence of fixes.

How the example maps to the code
In the example	In the code
What you typed and what you meant	Strings `a` and `b`
Cheapest fix for the first `i` and `j` letters	`dist[i][j]`
Delete a letter you typed	`dist[i - 1][j] + 1`
Type a missing letter	`dist[i][j - 1] + 1`
Overwrite a wrong letter	`dist[i - 1][j - 1] + 1`

From the slow way to edit distance

Start with brute force: try every sequence of edits and keep the shortest one that turns a into b. There is no limit on the number of sequences, so you must search by length: all one-edit changes, then all two-edit changes, and so on. Each edit can be made at any position, with any letter, so the number of candidates explodes after just a few steps.
Look at the last characters instead. To turn the first i characters of a into the first j characters of b, the last character of b must come from somewhere. Either it was inserted, or the last character of a was deleted first, or the two last characters were lined up. Lining them up is free when they are equal and costs one replace when they differ.
Each of those choices leaves a smaller version of the same question about two prefixes. So the state is the pair (i, j), and there are only (m + 1) × (n + 1) pairs. Store each answer once in a table dist.
The edges are known without work: turning i characters into nothing takes i deletes, and building j characters from nothing takes j inserts. Every other cell reads its neighbors above, to the left, and diagonally, so row-by-row order works. The bottom-right cell is the answer. That double loop is edit distance.

How it works

Make a table dist with a.length + 1 rows and b.length + 1 columns.
Fill column 0 with dist[i][0] = i: turning i characters into an empty string takes i deletes.
Fill row 0 with dist[0][j] = j: building j characters from nothing takes j inserts.
For every other cell, if a[i - 1] === b[j - 1], no edit is needed for those two: dist[i][j] = dist[i - 1][j - 1].
Otherwise take 1 plus the smallest of delete (dist[i - 1][j]), insert (dist[i][j - 1]), and replace (dist[i - 1][j - 1]).
Return dist[a.length][b.length].

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function editDistance(a, b) {
const rows = a.length;
const cols = b.length;
const dist = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
for (let i = 0; i <= rows; i++) dist[i][0] = i;
for (let j = 0; j <= cols; j++) dist[0][j] = j;
for (let i = 1; i <= rows; i++) {
for (let j = 1; j <= cols; j++) {
if (a[i - 1] === b[j - 1]) {
dist[i][j] = dist[i - 1][j - 1];
} else {
dist[i][j] = 1 + Math.min(dist[i - 1][j], dist[i][j - 1], dist[i - 1][j - 1]);
}
}
}
return dist[rows][cols];
}

How fast it is

Time	`O(m × n)`
Extra memory	`O(m × n)`

Every pair of prefixes gets one cell with a three-way minimum. Two rows are enough for the number, which uses O(n) space.

Best caseO(m × n)
Any input, even two identical strings: every cell is still filled.
Average caseO(m × n)
Any input: one comparison and at most a three-way minimum per cell.
Worst caseO(m × n)
The same. Two 10,000-character texts need 100 million cells, which is slow and uses a lot of memory.

Common mistakes

Leaving row 0 and column 0 at 0. Turning "abc" into "" costs 3, not 0.
Adding 1 when the characters match. A match is free: copy the diagonal cell.
Mixing up which neighbor means insert and which means delete. It doesn't change the plain distance, but it matters when the costs differ.
Comparing strings with different letter case or accents and getting surprising distances. Normalize both, for example with toLowerCase(), when the question allows it.

When to use it

Look for these clues in a problem:

Two strings and the question asks how different they are, or the fewest changes to turn one into the other.
The allowed operations are insert, delete, and replace, sometimes with different costs.
You need to find the closest match to a word in a list, as in autocomplete or spelling hints.
The answer is about whole strings, not just a common part.

Check yourself

Answer each one in your head first, then open it.

Why is dist[i][0] equal to i?

Turning i characters into an empty string needs exactly i deletes, and nothing can be faster, since each edit removes at most one character.

Why is a match free, copying the diagonal?

If the last characters are equal, you can keep both and only fix the prefixes before them. No edit is needed for that pair.

In the trace, why is dist[1][2] equal to 1?

"r" to "tr" needs one insert: put t in front. The r matches, so the cell copies dist[0][1], which is 1.

If edit distance is 0, what do you know about the strings?

They are identical. Any difference needs at least one edit.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

#537One Keystroke Away

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The table keeps one promise: when the loops reach cell (i, j), its neighbors above, to the left, and diagonally up-left already hold the true fewest edits between their prefixes. Row 0 and column 0 are right from the start, since an empty string only needs inserts or deletes.

Filling the cell keeps the promise. Look at the last step of a cheapest edit sequence for these two prefixes. The last character of a was deleted, leaving dist[i - 1][j] edits before it. Or the last character of b was inserted, leaving dist[i][j - 1]. Or the two last characters were lined up, leaving dist[i - 1][j - 1] plus 0 for a match or 1 for a replace. A cheapest sequence's earlier part must be cheapest too, or it could be swapped for a cheaper one.

On a match, the code copies the diagonal without comparing the other two. That is safe because neighbor cells in this table differ by at most 1, so dist[i - 1][j] + 1 and dist[i][j - 1] + 1 are never smaller than dist[i - 1][j - 1]. Every cell is filled once in an order that reads only finished cells, so the corner holds the full answer.

Going deeper

4 more ideas

What each cell of the table means

dist[i][j] is the fewest edits that turn a.slice(0, i) into b.slice(0, j). Moving down a row means one more character of a to deal with. Moving right means one more character of b to build. The diagonal means dealing with one character of each.

Why the three neighbors cover every case

Look at the last edit in a cheapest sequence. Either the last character of a was deleted (the rest is dist[i - 1][j]), or the last character of b was inserted (dist[i][j - 1]), or the last characters were lined up with each other, which costs nothing if they match and one replace if not (dist[i - 1][j - 1]).

How much work it does

One cell for each pair of prefixes: O(m * n) time and space. Each row only reads the row above, so two rows are enough for the number alone. For "did you mean" with a cutoff k, you can stop early once every cell in a row is bigger than k.

Variations

With different costs, add insertCost, deleteCost, or replaceCost instead of 1. Allowing a swap of two neighbor letters (teh to the) adds a fourth option that reads dist[i - 2][j - 2]. Pattern matching with wildcards uses the same table with true or false cells.

Work it by hand

Every step in a table, with why

Find the fewest edits that turn one 5-letter word into another made of almost the same letters. Each row of the trace is one full row of dist.

a = "react", b = "trace"

Step	`i`	`a[i - 1]`	`dist[i]`, `j` = 0 to 5	What happens	Why
1	0	-	0, 1, 2, 3, 4, 5	Build `b` from nothing	Line 6: making the first `j` letters of "trace" from an empty string takes `j` inserts.
2	1	r	1, 1, 1, 2, 3, 4	`r` matches at `j = 2`	`dist[1][1]` replaces `r` with `t` (1). `dist[1][2]` is free on the match and copies the diagonal 1: insert `t`, keep `r`.
3	2	e	2, 2, 2, 2, 3, 3	`e` matches at `j = 5`	At the last column, `e` matches `e`, so the cell copies `dist[1][4] = 3`.
4	3	a	3, 3, 3, 2, 3, 4	`a` matches at `j = 3`	"rea" to "tra" copies the diagonal 2 from "re" to "tr".
5	4	c	4, 4, 4, 3, 2, 3	`c` matches at `j = 4`	"reac" to "trac" stays at 2, again from the diagonal.
6	5	t	5, 4, 5, 4, 3, 3	`t` matches at `j = 1`	The corner: `t` and `e` differ, so it is 1 plus the smallest of 3, 3, and 2. The loops end and line 16 returns it.

It returns 3: insert t at the front, delete the e, and replace the final t with e. Another 3-edit answer replaces the first, second, and last letters. The table gives the number, not which script.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Edit distance	`O(m × n)`	`O(m × n)`	Strings of up to a few thousand characters, or when you need the list of edits.
Edit distance with two rows	`O(m × n)`	`O(n)`	Only the number is needed, and the strings are long.
Banded edit distance	`O(n · k)`	`O(n)`	You only care whether the distance is at most a small `k`, as in spelling suggestions.
Insert and delete only, through LCS	`O(m × n)`	`O(m × n)`	Replace isn't allowed. Then the distance is `m + n - 2 × LCS`.

Extra memory: O(m × n) for the table. Each row only reads the row above, so two rows of n + 1 numbers give O(n) space when you only need the number.

How the steps grow

Edit distance, Edit distance with two rows, Banded edit distance, Insert and delete only, through LCS O(m × n)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Edit distance	100	1 million	1 trillion
Edit distance with two rows	100	1 million	1 trillion
Banded edit distance	100	1 million	1 trillion
Insert and delete only, through LCS	100	1 million	1 trillion

Inputs that need care

5 tricky inputs

One string is empty: a = "", b = "abc": The table is one row: 0, 1, 2, 3. It returns 3, three inserts.
Identical strings: Every diagonal cell is a match, so it returns 0.
Same letters, different order: "listen" and "silent": It returns 4. Edit distance has no move or swap operation, so reordering costs inserts, deletes, and replaces.
Emoji or other characters outside the basic range: Strings index by UTF-16 code units, and an emoji is two of them. "a" to an emoji gives 2 instead of 1. Pass Array.from(a) and Array.from(b) to compare whole characters.
Different letter case: "Color" and "color": It returns 1, since C and c are different characters. Lowercase both first if case shouldn't count.

Variations and follow-ups

Twists interviewers add

Different costs per edit

Replace the 1 + with the cost of each edit: dist[i - 1][j] + deleteCost, and so on. With costs, the match shortcut is still safe as long as every edit costs something, and the edges become running sums of insert or delete costs.

Swapping neighbor letters

Typing teh for the is one swap. Add a fourth option: if the last two letters of each prefix are swapped copies of each other, read dist[i - 2][j - 2] + 1. This is the Damerau version of edit distance.

Only checking "within `k` edits"

For "did you mean" with a limit of k, only cells within k of the diagonal can be k or less. Filling only that band takes O(n · k) time, and you can stop once a whole row is above k.

Rebuilding the edit script

Start at the corner and, at each cell, move to the neighbor that produced its value: up means delete, left means insert, and diagonal means keep or replace. Reversing the moves gives the list of edits.

In an interview

Spot it, explain it, answer follow-ups

Spot it from "fewest operations to turn one string into another", with inserts, deletes, and replacements, or from spelling suggestions and fuzzy search.
Name the three neighbors out loud before coding: up is delete, left is insert, diagonal is keep or replace. Then say the edges: column 0 is all deletes, row 0 is all inserts.
Check the edges with a tiny case, like "ab" to "" (2) and "" to "ab" (2), and one where a match must be free, like "ab" to "b" (1).
Expect "how would you print the edits?" (walk back from the corner) and "how do you make it faster for spell checking?" (stop early with a band of width k, or compare against a trie of words).

Where frontend code uses it

The same idea in real UI code

The TypeScript compiler's "Did you mean...?" suggestions for misspelled names pick close candidates by edit distance.
Search boxes and command palettes use edit distance (often with a small cutoff like 2) to tolerate typos.
Form validation can suggest a fix for a likely typo in an email domain, such as gmial.com, by finding the known domain at the smallest distance.

Edit distance

The idea

An everyday example

Fixing a typo with the fewest keystrokes

From the slow way to edit distance

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

What each cell of the table means

Why the three neighbors cover every case

How much work it does

Variations

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Different costs per edit

Swapping neighbor letters

Only checking "within `k` edits"

Rebuilding the edit script

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Fixing a typo with the fewest keystrokes

From the slow way to edit distance

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

What each cell of the table means

Why the three neighbors cover every case

How much work it does

Variations

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Different costs per edit

Swapping neighbor letters

Only checking "within k edits"

Rebuilding the edit script

In an interview

Where frontend code uses it

Related algorithms

Only checking "within `k` edits"