📊 Edit Distance — Dynamic Programming

Strings (letters, ≤ 8)

source

target

Work to solve

naive recursion2,187 calls

DP table20 cells

The table computes each subproblem once instead of re-deriving it exponentially.

Edit Distance Recurrence

1dp[i][0] = i;  dp[0][j] = j            // base
2for i in 1..m:
3  for j in 1..n:
4    if a[j-1] == b[i-1]:
5      dp[i][j] = dp[i-1][j-1]          // match
6    else: dp[i][j] = 1 + min(
7      left dp[i][j-1], up dp[i-1][j], diag dp[i-1][j-1])

Speed: 55%

Edit Distance Visualizer: Dynamic Programming Table You Fill Yourself

This edit distance simulator turns the classic dynamic-programming table into something you can watch and do. Each interior cell lights up with arrows to its three dependencies — left (insert), up (delete), diagonal (match or replace) — and the readout explains whether the letters match (copy the diagonal) or cost 1 + the cheapest neighbor. When the table completes, the optimal alignment path glows gold from the bottom-right answer back to the origin, showing exactly which edits transform one word into the other. The signature interaction: Fill-It-Yourself mode asks you to type each cell's value from its neighbors with instant feedback and a streak counter — active recall of the recurrence instead of passive watching. A work-to-solve card contrasts the naive recursion's exponential call count with the table's m·n cells, and both strings are editable so you can compute the distance between any two words.

What you can do in this simulation

Watch the DP table fill cell by cell with dependency arrows showing left / up / diagonal and which neighbor the value came from
Switch to Fill-It-Yourself and type each cell's value from its three neighbors, with instant feedback, explanations, and a streak counter
See the optimal alignment path traced in gold when the table completes — the exact inserts, deletes, and replacements
Edit both strings (cat→cart, kitten→sitting, sunday→saturday presets included) and recompute instantly
Compare the naive recursion's exponential calls with the table's m·n cells in the work-to-solve card

Concepts covered

edit distance · levenshtein distance · dynamic programming · DP table · optimal substructure · backtrace alignment · string algorithms

Related simulations

Browse all Technology simulations →

Free to use in your browser — no signup required. Found a bug or have an idea to make it better? Tell us.

Please wait

Loading technology simulations

The requested content is still loading.

Finished experimenting?

Save one completion to this browser's signed guest ledger, or directly to your account when signed in.

1dp[i][0] = i; dp[0][j] = j // base

2for i in 1..m:

3 for j in 1..n:

4 if a[j-1] == b[i-1]:

5 dp[i][j] = dp[i-1][j-1] // match

6 else: dp[i][j] = 1 + min(

7 left dp[i][j-1], up dp[i-1][j], diag dp[i-1][j-1])

Edit Distance Visualizer: Dynamic Programming Table You Fill Yourself

What you can do in this simulation

Watch the DP table fill cell by cell with dependency arrows showing left / up / diagonal and which neighbor the value came from

Switch to Fill-It-Yourself and type each cell's value from its three neighbors, with instant feedback, explanations, and a streak counter

See the optimal alignment path traced in gold when the table completes — the exact inserts, deletes, and replacements

Edit both strings (cat→cart, kitten→sitting, sunday→saturday presets included) and recompute instantly

Compare the naive recursion's exponential calls with the table's m·n cells in the work-to-solve card