Pattern Recognition Drill

#69 — Edit distance

Medium Dynamic Programming

The Problem

Minimum operations (insert, delete, replace) to convert word1 into word2.

What approach would you use?

Think about it before scrolling down.

Key Signals

'Transform one string to another' + 'minimum operations' → classic DP on strings
2D table: dp[i][j] = edit distance between word1[:i] and word2[:j]
Three choices at each position: insert, delete, replace

Dynamic Programming

2D DP. If chars match, dp[i][j] = dp[i-1][j-1]. Else min(insert, delete, replace) + 1. O(m*n).

Common Trap

No greedy shortcut exists. The 2D DP is the canonical approach — know it cold.

← #68 #70 →