Edit Distance

1. Problem Description

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

You can 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)
	}

	// If they are equal, no operation is needed
	if word1[0] == word2[0] {
		return minDistance(word1[1:], word2[1:])
	} else {
		// If they are different, delete the first character of word1, leaving word1[1:] while word2 stays unchanged
		deleted := 1 + minDistance(word1[1:], word2)
		// If they are different, replace the first character of word1 so word1[0] equals word2[0], then compare word1[1:] and word2[1:]
		updated := 1 + minDistance(word1[1:], word2[1:])
		// If they are different, insert the first character of word2 before word1 so the inserted character equals word2[0], then compare word1 with word2[1:]
		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

func minDistance(word1 string, word2 string) int {
    memo := make(map[string]int, 0)
    return minDistanceDFS(word1, 0, word2, 0, memo)
}

func minDistanceDFS(word1 string, index1 int, word2 string, index2 int, memo map[string]int) int {
    key := buildKey(index1, index2)
    count, ok := memo[key]
    if ok {
        return count
    }
    
    if index1==len(word1) {
        count = len(word2)-index2
        memo[key] = count
        return count
    }
    if index2==len(word2) {
        count = len(word1)-index1
        memo[key] = count
        return count
    }

    if word1[index1] == word2[index2] {
        count = minDistanceDFS(word1, index1+1, word2, index2+1, memo)
    }else {
        // If they are different, delete the current character of word1 while word2 stays unchanged
        deleted := 1+minDistanceDFS(word1, index1+1, word2, index2, memo)
        // If they are different, replace the current character of word1 so it equals word2[index2], then advance both indexes
        updated :=  1+minDistanceDFS(word1, index1+1, word2, index2+1, memo)
        // If they are different, insert the current character of word2 at the current position in word1, then keep index1 and advance index2
        inserted := 1+minDistanceDFS(word1, index1, word2, index2+1, memo)
        count = min(deleted,updated,inserted)
    }
    memo[key] = count
    return count
}

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

func buildKey(index1, index2 int) string{
    return fmt.Sprintf("%d_%d", index1, index2)
}

4. References

• Brute-force DFS -> Memoized DFS -> State-transition DP - Edit Distance - LeetCode