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.

Why this is worth learning

A state compares two complete prefixes. Classify the last alignment step as a match, replacement, deletion, or insertion; each action removes at least one final byte from consideration.

Before coding: one-minute experiment

For "cat" to "cut", which predecessor explains distance 1? What are the costs from an empty string to "cut"?

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

Let E(i,j) be the minimum unit-cost edits changing word1[:i] into word2[:j]. Transforming a nonempty prefix to empty requires i deletions; constructing a prefix from empty requires j insertions. Equal final bytes can align at no cost, leaving E(i-1,j-1). Otherwise the final edit is replacement, deletion, or insertion, whose predecessor costs are respectively diagonal, above, and left; minimizing them and adding one covers every optimal alignment and constructs a valid one. In the rolled row, save the old diagonal before overwriting each cell and carry it to the next column.

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.

Debugging lens

Test either empty input, identical strings, repeated bytes, and a substitution versus delete-plus-insert. This API indexes Go string bytes: one non-ASCII character may occupy multiple positions.

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.

Contract precision

Distance is over bytes, not Unicode code points or grapheme clusters. Insert/delete/replace each cost 1. Changing to rune-based semantics would be an observable API change.

Reconstruction checkpoint

For "cat" to "cut", which predecessor explains distance 1? What are the costs from an empty string to "cut"?

Return to 2D DP · Module quiz