Edit Distance

Problem

You are given two strings word1 and word2. In one operation you may insert a character, delete a character, or replace a character anywhere in word1. Return the fewest operations needed to turn word1 into word2.

• 0 <= len(word1), len(word2) <= 500
• Both strings consist of lowercase English letters.

Examples

• word1 = "saturday", word2 = "sunday" → 3. Delete a, delete t, replace r→n.
• word1 = "planet", word2 = "plane" → 1. Delete the trailing t.
• word1 = "", word2 = "xyz" → 3. Only insertions are possible from an empty string.

Hints

1. Look at the last characters of both strings. If they match, do you ever need to touch them?
2. If they differ, the last operation must be exactly one of insert, delete, or replace. Each one leaves you with a smaller subproblem.
3. 2D DP on prefix lengths: dp[i][j] = distance between word1[:i] and word2[:j].