DSA Tracker

Visualize

Edit Distance

Fill a table where every cell asks the same question about shorter prefixes

time O(m*n)space O(m*n)

Compare the last letters of the two prefixes. If they are equal, they cost nothing and the answer is whatever it took to fix everything before them — the diagonal cell. If they differ, one edit is unavoidable, and the three ways to spend it each land on a neighbour already computed: replace comes from the diagonal, delete from the cell above, insert from the cell to the left. Take the cheapest and add one. The arrows in the table are that recurrence made visible.

Details

Animated on: Turn "kitten" into "sitting" using insertions, deletions and replacements — what is the fewest edits?

Problem:Edit DistanceMedium

Fill a table where every cell asks the same question about shorter prefixes

step 1 / 12

rows = prefixes of "kitten", columns = prefixes of "sitting"

dp[i][j] is the cheapest way to turn the first i letters of "kitten" into the first j of "sitting". Two empty prefixes already match, so dp[0][0] = 0.

Pseudocode
1FUNCTION editDistance(a, b)
2  m <- LENGTH(a)
3  n <- LENGTH(b)
4  FOR i FROM 0 TO m
5    dp[i][0] <- i
6  FOR j FROM 0 TO n
7    dp[0][j] <- j
8  FOR i FROM 1 TO m
9    FOR j FROM 1 TO n
10      IF a[i-1] = b[j-1]
11        dp[i][j] <- dp[i-1][j-1]
12      ELSE
13        dp[i][j] <- 1 + MIN(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
14  RETURN dp[m][n]

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. dp[i][j] is the cheapest way to turn the first i letters of "kitten" into the first j of "sitting". Two empty prefixes already match, so dp[0][0] = 0.
  2. With nothing to match against, the only move is deleting. Turning all 6 letters of "kitten" into "" costs dp[6][0] = 6 deletions.
  3. Same argument mirrored: building "sitting" out of "" needs dp[0][7] = 7 insertions. Every other cell is now reachable from three neighbours already on the board.
  4. 'k' does not match 's', so one edit is unavoidable: replace 0, delete 1, insert 1. Cheapest is 0, so dp[1][1] = 1 by choosing to replace 'k' with 's'.
  5. 'k' does not match 'i', so one edit is unavoidable: replace 1, delete 2, insert 1. Cheapest is 1, so dp[1][2] = 2 by choosing to replace 'k' with 'i'.
  6. 'i' and 'i' are the same letter, so the last character costs nothing — dp[2][2] just inherits the diagonal, 1. One arrow, no +1.
  7. 't' and 't' are the same letter, so the last character costs nothing — dp[3][3] just inherits the diagonal, 1. One arrow, no +1.
  8. 't' and 't' are the same letter, so the last character costs nothing — dp[4][4] just inherits the diagonal, 1. One arrow, no +1.
  9. 'e' does not match 'i', so one edit is unavoidable: replace 1, delete 2, insert 2. Cheapest is 1, so dp[5][5] = 2 by choosing to replace 'e' with 'i'.
  10. 'n' and 'n' are the same letter, so the last character costs nothing — dp[6][6] just inherits the diagonal, 2. One arrow, no +1.
  11. 'n' does not match 'g', so one edit is unavoidable: replace 3, delete 4, insert 2. Cheapest is 2, so dp[6][7] = 3 by choosing to insert 'g'.
  12. dp[6][7] = 3: "kitten" becomes "sitting" in 3 edits, and every cell on the way is a smaller version of the same question.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Edit Distance in the editorAll Dynamic Programming problemsBack to roadmap