编辑距离

1. 题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符 删除一个字符 替换一个字符

2. 思路

• 递归
• 递归+缓存

3. 实现

3.1. 递归

package main

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

	//相等那么不需要做任何操作
	if word1[0] == word2[0] {
		return minDistance(word1[1:], word2[1:])
	} else {
		//不相等可以删除word1的第一个字符，这样word1就剩下word[1:]，而word2没变化
		deleted := 1 + minDistance(word1[1:], word2)
		//不相等可以更新word1的第一个字符，这样word1[0]和word2[0]相等，继续比较word1[1:]和word2[1:]
		updated := 1 + minDistance(word1[1:], word2[1:])
		//不相等可以在word1前插入word2的第一个字符，这样新插入的字符和word2[0]相等，继续比较word1和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. 递归+缓存

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 {
        // 不相等可以删除word1的第一个字符，这样word1就剩下word[1:]，而word2没变化
        deleted := 1+minDistanceDFS(word1, index1+1, word2, index2, memo)
        // 不相等可以更新word1的第一个字符，这样word1[0]和word2[0]相等，继续比较word1[1:]和word2[1:]
        updated :=  1+minDistanceDFS(word1, index1+1, word2, index2+1, memo)
        // 不相等可以在word1当前位置插入word2的当前字符，这样新插入的字符和word2[index2]相等，继续比较word1和word2[index2+1:]
        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. 参考

• 暴力 DFS -> 记忆优化 DFS -> 状态转移 DP - 编辑距离 - 力扣（LeetCode）