Problem Statement

Edit Distance

You have two words, word1 and word2. You are allowed three moves: insert a letter, delete a letter, or replace one letter with another. The question asks: what is the smallest number of moves needed to turn word1 into word2? For example, turning "horse" into "ros" takes 3 moves.

hardDynamic ProgrammingDynamic ProgrammingTime: O(m*n) · Space: O(m*n)

Signals to notice

transform one string into anotherinsert/delete/replace operationsminimum cost

Brute force first

Try all possible sequences of operations recursively. Three choices at each mismatch, leading to exponential branching. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

2D DP: dp[i][j] = min operations to convert word1[0.i-1] to word2[0.j-1]. If characters match, dp[i][j] = dp[i-1][j-1]. Otherwise, min of insert (dp[i][j-1]+1), delete (dp[i-1][j]+1), replace (dp[i-1][j-1]+1). Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `word1="horse", word2="ros"`

Init: dp[0]=[0,1,2,3]; base col dp[i][0]=i (cost to delete i chars)
i=1 'h' (all mismatch vs r,o,s): dp[1]=[1,1,2,3]
i=2 'o' ('o'=='o' match -> dp[1][1]=1): dp[2]=[2,2,1,2]
i=3 'r' ('r'=='r' match -> dp[2][0]=2): dp[3]=[3,2,2,2]
i=4 's' ('s'=='s' match -> dp[3][2]=2): dp[4]=[4,3,3,2]
i=5 'e' (all mismatch; last = 1+min(2,4,3)=3): dp[5]=[5,4,4,3]
return dp[5][3] = 3 (horse->rorse->rose->ros)

What must stay true

dp[i][j] represents the exact minimum cost to align the first i characters of word1 with the first j characters of word2. Each cell depends only on three neighbors — left, above, and diagonal. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

dp[i][0]=i, dp[0][j]=j   // base: turn prefix into empty string
for i in 1..m, for j in 1..n:
  if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]   // free, chars align
  else: dp[i][j]=1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])  // del/ins/replace
return dp[m][n]

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Confusing which operation maps to which cell transition. Insert = move right (dp[i][j-1]), delete = move down (dp[i-1][j]), replace = move diagonally (dp[i-1][j-1]). The fix is usually to return to the meaning of each move, not just the steps themselves.

Dynamic Programming Pattern