Edit Distance

Medium

The problem

You may change word1 with three kinds of single-step edits: insert a character, delete a character, or replace one character with another. Return the fewest edits needed to turn word1 into word2.

Example 1
Input: word1 = "horse", word2 = "ros"
Output: 3
horse becomes rorse (replace h with r), then rose (delete r), then ros (delete e).
Example 2
Input: word1 = "intention", word2 = "execution"
Output: 5

Limits

0 ≤ len(word1), len(word2) ≤ 500
Both words have only lowercase English letters

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Insert, delete and replace each correspond to moving in a different direction in the table.

The idea

dp[i][j] = dp[i−1][j−1] if the characters match, else 1 + min(insert dp[i][j−1], delete dp[i−1][j], replace dp[i−1][j−1]).

Target: O(m·n) time

Go function shape

func minDistance(word1 string, word2 string) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MinDistance: fewest insert / delete / replace edits to turn a into b.
// State: dp[i][j] = edits to turn a[:i] into b[:j].
func MinDistance(a, b string) int {
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
		dp[i][0] = i // delete everything
	}
	for j := 0; j <= len(b); j++ {
		dp[0][j] = j // insert everything
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) // replace, delete, insert
			}
		}
	}
	return dp[len(a)][len(b)]
}

Read the lesson: 2-D Dynamic Programming