Edit Distance

Given two strings, return the minimum number of operations (insert, delete, replace) required to convert word1 to word2. Brute-force recursion over edits is exponential.

Function signature

func MinDistance(word1, word2 string) int

Inputs / outputs

• word1, word2: input strings.
• Return: minimum edit distance.

Example

word1 = "horse", word2 = "ros"
horse -> rorse (replace h)
rorse -> rose (delete r)
rose -> ros (delete e)
Output: 3

Constraints

• 0 <= len(word1), len(word2) <= 500

Core idea (near-solution)

2D DP: dp[i][j] is the edit distance between prefixes word1[:i] and word2[:j].

Invariant: dp[i][j] is correct once dp[i-1][j], dp[i][j-1], dp[i-1][j-1] are known.

Algorithm (step-by-step)

1. Initialize dp[0][j] = j and dp[i][0] = i.
2. For i from 1..m, j from 1..n:
   • If chars equal, dp[i][j] = dp[i-1][j-1].
   • Else dp[i][j] = 1 + min(replace, delete, insert).
3. Return dp[m][n].

Correctness sketch

• Invariant: dp[i][j] is correct once dp[i-1][j], dp[i][j-1], dp[i-1][j-1] are known.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

Example input:
word1 = "horse", word2 = "ros"
horse -> rorse (replace h)
rorse -> rose (delete r)
rose -> ros (delete e)
Output: 3

Walk:
- horse -> rorse (replace h)
- rorse -> rose (delete r)
- rose -> ros (delete e) -> 3

Pitfalls to avoid

• Off-by-one in dp sizing (needs m+1 by n+1).
• Mixing up insert/delete indices.

Complexity

• Time: O(m*n).
• Extra space: O(n) with rolling array.

Implementation notes (Go)

• Rolling DP is safe: keep prev (dp[i-1][j-1]) while iterating columns.