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.

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

python

▶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

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.

06

Complexity

Time

O(m·n)

Space

O(m·n)

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