How does the dynamic programming table work?

You build a grid where cell dp[i][j] holds the edit distance between the first i characters of string A and the first j characters of string B. The first row and column are the base cases (turning a string into the empty string costs its length). Every other cell is filled from three neighbors: diagonal (match or replace), up (delete), and left (insert).

What is the edit distance recurrence?

If the current characters match (A[i-1] == B[j-1]), then dp[i][j] = dp[i-1][j-1] — no edit needed. Otherwise dp[i][j] = 1 + min(dp[i-1][j-1] for replace, dp[i-1][j] for delete, dp[i][j-1] for insert). The answer is the bottom-right cell, dp[m][n].

What is the time and space complexity?

Filling the full table takes O(m·n) time and O(m·n) space for strings of length m and n. If you only need the final distance (not the path), you can keep just two rows and reduce the space to O(min(m, n)); recovering the actual edits, however, needs the full table or a divide-and-conquer trick.

What is edit distance used for?

Spell-checkers and autocorrect, fuzzy search and record matching, DNA and protein sequence alignment in bioinformatics, diff tools that compare files, plagiarism detection, and speech-recognition scoring all rely on edit distance or close variants of it.

ALGORITHMS · 11 / EDIT DISTANCE

The Typo Fixer.

How far is kitten from sitting? Not in letters — in edits. Watch a grid work out the fewest insert, delete, and replace moves to turn one word into the other, one cell at a time, then trace the cheapest path.

THE GIST · 20 SECONDS

Edit distance (the Levenshtein distance) is the fewest single-character insert / delete / replace edits to turn string A into string B. Build a grid: dp[i][j] is the distance between the first i letters of A and first j of B. If the letters match, copy the diagonal; else take 1 + the smallest of the diagonal (replace), up (delete), and left (insert). The answer waits in the bottom-right.

Insertadd a letter (← left)
Deletedrop a letter (↑ up)
Replaceswap a letter (↖ diag)
Matchfree — copy the diagonal

Hit Step to fill the next cell — or Play and watch the whole grid compute, then trace the cheapest edits.

UNDER THE HOOD

What you just played, written down

Every cell asks one small question and reuses answers already on the grid. That reuse — solving each subproblem once — is dynamic programming.

How edit distance thinks — four moves

Define the cell. dp[i][j] = edits to turn A's first i letters into B's first j letters.
Seed the edges. dp[i][0] = i (delete everything), dp[0][j] = j (insert everything). Turning a word into "" costs its length.
Match is free. If A[i-1] == B[j-1], the last letters already agree — copy the diagonal, dp[i-1][j-1]. No edit.
Otherwise pay 1. dp[i][j] = 1 + min( diagonal ↖ replace, up ↑ delete, left ← insert ). The answer is the bottom-right corner.

WHY THE DIRECTIONS MEAN THOSE EDITS

Moving ↖ diagonally consumes one letter of both words — a replace (or free match). Moving ↑ consumes a letter of A only — a delete. Moving ← consumes a letter of B only — an insert.

The whole thing in code

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    # base cases: turn a word into ""
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]      # match - free
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j-1],            # replace ↖
                    dp[i-1][j],              # delete  ↑
                    dp[i][j-1])              # insert  ←
    return dp[m][n]

TIMEO(m·n)every cell once

SPACEO(m·n)O(min) for value only

TWO ROWS ARE ENOUGH — FOR THE NUMBER

Each cell only reads the current and previous row, so you can drop to O(min(m,n)) space if you just want the distance. Recovering the actual edits needs the full grid (or Hirschberg's divide-and-conquer).

⚠ Ties = many optimal paths

When the diagonal, up, and left neighbors tie, there are several cheapest edit sequences. The traceback here prefers match/replace, then delete, then insert — any consistent rule finds a minimum.

↔ Its relatives

Longest Common Subsequence is the same grid with different rules; Needleman–Wunsch is edit distance with weighted gaps for DNA; Damerau–Levenshtein adds a transposition edit.

★ Where it's used

Spell-check & autocorrect, fuzzy search, diff tools, DNA/protein alignment, plagiarism detection, and scoring speech recognition against a reference.

SOLVE IT YOURSELF

Solve it: edit distance

This one is yours to write — in Python or TypeScript, running for real in your browser. Fill the DP table and return the bottom-right cell. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement edit_distance(a, b): return the minimum number of single-character insertions, deletions, and replacements to turn a into b. Build the (m+1) × (n+1) DP table and return dp[m][n].

HINTS — 4 IDEAS

Base cases: dp[i][0] = i and dp[0][j] = j — turning a word into "" costs its length.
If a[i-1] == b[j-1], the letters match: dp[i][j] = dp[i-1][j-1] (no edit).
Otherwise dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) — replace, delete, insert.
The answer is the bottom-right cell, dp[m][n].

CPython · WebAssembly

QUICK CHECK

Did it stick?

FAQ

Edit distance, answered

What is edit distance?

The Levenshtein distance — the fewest single-character insert, delete, and replace edits to turn one string into another. Turning kitten into sitting takes 3: replace k→s, replace e→i, insert g.

How does the DP table work?

dp[i][j] is the distance between A's first i letters and B's first j. The first row/column are base cases; every other cell is built from its diagonal, up, and left neighbors.

What's the recurrence?

If a[i-1]==b[j-1], dp[i][j]=dp[i-1][j-1] (match, free). Otherwise dp[i][j]=1+min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) — replace, delete, insert. Answer: dp[m][n].

What's the complexity?

O(m·n) time and space. For just the number you can keep two rows — O(min(m,n)) space — but recovering the edits needs the full grid.

Where is it used?

Spell-check & autocorrect, fuzzy search, diff tools, DNA/protein alignment (Needleman–Wunsch), plagiarism detection, and speech-recognition scoring.

▶ Watch it explained

Prefer a video walkthrough?

Finished this one? 0 / 99 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA