编辑距离

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 {
		//不相等可以删除
		deleted := 1 + minDistance(word1[1:], word2)
		//不相等可以更新
		updated := 1 + minDistance(word1[1:], 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. 递归+缓存

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
	//相等那么不需要做任何操作
	if word1[0] == word2[0] {
		res = minDistance(word1[1:], word2[1:])

	} else {
		//不相等可以删除
		deleted := 1 + minDistance(word1[1:], word2)
		//不相等可以更新
		updated := 1 + minDistance(word1[1:], word2[1:])
		//不相等可以插入
		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. 参考

• 72. 编辑距离 - 力扣（LeetCode）