Explore dynamic programming with interactive table updates and answer reconstruction. Follow each state transition and see how subproblems build a solution.
The fewest single-character edits that turn one string into the other. Each cell reads exactly three neighbours, and the arrow drawn to the winner is the edit operation itself.
Press Start to fill the edit distance table.
How it works: Edit Distance
Step by step
- Cell being computed
- Cells it reads (dashed arrows)
- Already computed
- Traceback path to the answer
Press Start or Step: the step the animation is on lights up below.
- 1
Fill the base row and column
Turning a prefix into the empty string takes one delete per letter, and building a prefix from nothing takes one insert per letter. These are the cells every other cell eventually leans on.
dp[i][0] = i; dp[0][j] = j - 2
Letters match → copy the diagonal
If the two current letters are equal, they cost nothing. The answer is whatever it took to align everything before them.
if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] - 3
Letters differ → 1 + cheapest neighbour
Pay for one edit and take the cheapest way in: replace (diagonal), delete from the first string (above), or insert into it (left). The solid arrow shows which one won.
else: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) - 4
Trace the cheapest path back
Walk from the bottom-right corner back to the start, at each cell stepping to the neighbour it came from. The steps spell out the actual edits, not just how many.
while (i, j) != (0, 0): step to the cell dp[i][j] came from - 5
The corner cell is the answer
dp[m][n] is the edit distance between the full strings.
return dp[m][n]
Edit distance is the fewest single-character inserts, deletes and replaces that turn one string into another. Trying every sequence of edits is exponential, but the problem has a small set of subproblems that keep repeating: how far apart are the first i letters of one string and the first j letters of the other?
Put those answers in a table, cell (i, j) for each pair of prefixes. A cell only depends on three neighbours, so filling it row by row means each one is computed exactly once. The bottom-right cell is the answer for the whole strings.
Each neighbour is one edit. Up-left is replace (or a free match), up is delete, and left is insert. That's why the arrow drawn to the winning neighbour is the edit itself.
Spot it in an interview
- “Minimum number of operations to convert A into B.”
- Spell checkers, DNA alignment, diff tools, and fuzzy search.
- Any two-string problem where the answer for whole strings builds from answers for shorter prefixes.
There's one cell per pair of prefixes, and each cell reads three neighbours, which is O(1) work. If you only need the number, keep two rows and space drops to O(min(m, n)), but then you can't trace the edits back.