Edit Distance — Step-by-Step Visualization

Algorithm Pattern

2D Dynamic Programming

Key Idea

We build a 2D matrix where dp[i][j] represents the minimum operations to convert word1[i:] to word2[j:]. When characters don't match, we choose the minimum of three possible future states: Insert, Delete, or Replace.

Step-by-Step Approach

1. Initialize a (m+1) x (n+1) grid, where m and n are the lengths of word1 and word2.
2. Fill the base cases: the distance to an empty string is simply the length of the remaining string.
3. Iterate through the grid from the bottom-right towards the top-left.
4. If word1[i] == word2[j], it costs nothing: dp[i][j] = dp[i+1][j+1].
5. Otherwise, the cost is 1 + min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) representing delete, insert, and replace respectively.

Common Gotchas

• Remember the grid size is (m+1) by (n+1) to account for empty string cases.
• The final answer is at dp[0][0] when using a bottom-up approach from the end.