LeetCode #72 Hard

Edit Distance

Minimum insert / delete / replace operations to turn word1 into word2.

dpstring

02

Intuition

Same skeleton as LCS: compare prefix pairs. dp[i][j] = cost to convert word1[:i] into word2[:j]. Matching last characters cost nothing — inherit the diagonal. Otherwise the last edit must be one of exactly three moves (replace, delete, insert), each reducing to a neighboring smaller subproblem — take the cheapest and add 1.

How to spot this pattern

Same grid as longest-common-subsequence, but minimising instead of maximising — and with a genuine base case rather than zeros. The three neighbours you consult are the three operations: diagonal is replace, up is delete, left is insert. Whenever a problem offers a fixed menu of moves that each consume a bit of the input, each move becomes one neighbour in the DP table.

03

Approach

1

Base cases are the frame

dp[i][0] = i (delete everything), dp[0][j] = j (insert everything).

2

Three moves, three neighbors

Mismatch at (i,j): replace → dp[i-1][j-1]+1, delete word1's char → dp[i-1][j]+1, insert word2's char → dp[i][j-1]+1. Match: dp[i-1][j-1] free.

3

Why this is complete

Any optimal edit script has some last operation touching the ends, and it must be one of these three (or a free match) — so the min over them is optimal. Classic Levenshtein distance.

04

Solution & live demo

▶1class Solution:
▶2    def minDistance(self, word1, word2):
▶3        m, n = len(word1), len(word2)
▶4        dp = [[0] * (n + 1) for _ in range(m + 1)]
▶5        for i in range(m + 1): dp[i][0] = i
▶6        for j in range(n + 1): dp[0][j] = j
▶7        for i in range(1, m + 1):
▶8            for j in range(1, n + 1):
▶9                if word1[i-1] == word2[j-1]:
▶10                    dp[i][j] = dp[i-1][j-1]
▶11                else:
▶12                    dp[i][j] = 1 + min(dp[i-1][j-1],   # replace
▶13                                       dp[i-1][j],     # delete
▶14                                       dp[i][j-1])     # insert
▶15        return dp[m][n]

05

Common pitfalls

Leaving the first row and column at zero

✗ Wrong

dp = [[0] * (n + 1) for _ in range(m + 1)]
# straight into the loops

✓ Right

for i in range(m + 1): dp[i][0] = i
for j in range(n + 1): dp[0][j] = j

Turning a 5-character word into the empty string costs 5 deletions, not 0. Unlike LCS, the empty-prefix cases here are non-zero, and leaving them empty makes every distance too small.

Adding 1 on a character match

✗ Wrong

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1

✓ Right

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]

Matching characters need no edit at all — you advance both strings for free. This is exactly inverted from LCS, where a match is the only time the count grows, and copying that habit across is the usual slip.

Taking the min over only two neighbours

✗ Wrong

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])

✓ Right

dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

Dropping the diagonal removes replace from the menu, so a single substitution gets billed as a delete plus an insert. "cat" to "cut" then reports 2 instead of 1.

06

Edge cases

One word empty

Answer is the other word's length (all inserts or all deletes).

Equal words

Diagonal is free all the way — 0.

Completely disjoint alphabets

max(m,n): replace along the diagonal, insert/delete the remainder.

07

Complexity

Time

O(m·n)

Space

O(m·n)

Two rows give O(n) space; full table needed only to recover the edit script.