The fewest inserts, deletes and replaces to turn one word into another. Fill a table where each cell takes the cheapest of three neighbours.
▼The problem
LeetCode 72 (Hard). Given two words, return the fewest operations that turn word1 into word2, where an operation inserts a letter, deletes a letter, or replaces one letter with another.
Example: "horse" → "ros" takes 3 edits: replace H with R (rorse), delete the middle R (rose), delete E (ros).
The solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i # delete all
for j in range(n + 1): dp[0][j] = j # insert all
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # keep
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]Transcript
Edit Distance. Given two words, find the fewest edits that turn the first into the second. An edit inserts, deletes, or replaces one letter.
Take horse and R, O, S. Three edits: replace the H with an R, delete the middle R, and delete the E.
The naive way tries every edit at every position, recursively. Each step branches three ways, so the work grows exponentially, redoing the same pieces.
Instead, build a table. Cell i, j holds the fewest edits to turn the first i letters of horse into the first j letters of R, O, S. The top row and left column count up from zero: from nothing you insert, to nothing you delete. If the letters match, copy the cell up and left. If they differ, take one plus the smallest of three neighbours: up left to replace, up to delete, or left to insert.
In code, set the first row and column, then two loops fill the rest, one minimum per cell.
Let's fill it. H against R: they differ, so one plus zero, one. O against O: they match, so copy the diagonal. The rest fill the same way until the corner says three. Trace back from the corner: delete E, keep S, delete R, keep O, replace H with R.
With m and n letters, there are m times n cells, so the time is order m times n. The table takes the same space, though one row, updated in place, is enough.
Small pieces first, then build up. That's Edit Distance.