Pattern visualizer

Edit Distance

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. Animated on: Turn "kitten" into "sitting" using insertions, deletions and replacements — what is the fewest edits?.

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

time O(m*n)space O(m*n)step 1 / 12

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

-sitting

-kitten

line 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.

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

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap