Edit Distance

1. Problem Description

Given two words word1 and word2, calculate the minimum number of operations required to convert word1 into word2.

You may perform the following three operations on a word:

Insert a character Delete a character Replace a character

2. Approach

• Recursion
• Recursion + cache

3. Implementation

3.1. Recursion

package main

func minDistance(word1 string, word2 string) int {
	if len(word1) == 0 || len(word2) == 0 {
		return len(word1) + len(word2)
	}

	// Equal, so no operation is needed
	if word1[0] == word2[0] {
		return minDistance(word1[1:], word2[1:])
	} else {
		// If unequal, delete
		deleted := 1 + minDistance(word1[1:], word2)
		// If unequal, replace
		updated := 1 + minDistance(word1[1:], word2[1:])
		// If unequal, insert
		inserted := 1 + minDistance(word1, word2[1:])
		return Min(inserted, deleted, updated)
	}
}

func Min(nums ...int) int {
	min := nums[0]
	for _, num := range nums {
		if num < min {
			min = num
		}
	}

	return min
}

3.2. Recursion + Cache

package main

import "fmt"

var cache = make(map[string]int, 0)

func minDistance(word1 string, word2 string) int {
	if len(word1) == 0 || len(word2) == 0 {
		return len(word1) + len(word2)
	}

	count, ok := cache[fmt.Sprintf("%s_%s", word1, word2)]
	if ok {
		return count
	}
	var res int
	// Equal, so no operation is needed
	if word1[0] == word2[0] {
		res = minDistance(word1[1:], word2[1:])

	} else {
		// If unequal, delete
		deleted := 1 + minDistance(word1[1:], word2)
		// If unequal, replace
		updated := 1 + minDistance(word1[1:], word2[1:])
		// If unequal, insert
		inserted := 1 + minDistance(word1, word2[1:])
		res = Min(inserted, deleted, updated)
	}

	cache[fmt.Sprintf("%s_%s", word1, word2)] = res
	return res

}

func Min(nums ...int) int {
	min := nums[0]
	for _, num := range nums {
		if num < min {
			min = num
		}
	}

	return min
}

4. References

• 72. Edit Distance - LeetCode