老卫带你学---leetcode刷题(72. 编辑距离)

72. 编辑距离

问题：

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

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

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

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
1
2
3
4
5
6
7
8

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
1
2
3
4
5
6
7
8
9
10

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
1
2
3
4

解决：

这道题其实就是典型的搜索问题，并且可以分解为多个相同子问题，那就直接上备忘录，记录已经解决的子问题，简单效果好。

记忆化搜索—>DFS+备忘录

//声明全局备忘录，不要在函数里初始化，再通过传参的方式来玩，这样效率极低
var dp [][]int

func minDistance(word1 string, word2 string) int {
	//初始化dp备忘录
	dp = make([][]int, len(word1)+1)
	for i := range dp {
		dp[i] = make([]int, len(word2)+1)
	}

	for i := 0; i < len(word1)+1; i++ {
		for j := 0; j < len(word2)+1; j++ {
			dp[i][j] = -1
		}
	}
	return dfs(len(word1), len(word2), word1, word2)
}

func dfs(i, j int, word1, word2 string) int {
	if dp[i][j] != -1 {
		return dp[i][j]
	}
	//搜索终止条件
	if i==0{
		return j
	}
	if j==0{
		return i
	}
	//如果搜索过程中word1[i-1] == word2[j-1]，那就dp结果和上一位一致，很好理解
	if word1[i-1] == word2[j-1] {
		h := dfs(i-1, j-1, word1, word2)
		dp[i][j] = h
		return h
	} else {
		inserted := dfs(i, j-1, word1, word2) //插入可以理解为将原来word2的j位置的元素干掉
		deleted := dfs(i-1, j, word1, word2)//删除可以理解为在原来word1的i位置的元素干掉
		replaced := dfs(i-1, j-1, word1, word2) //替换会和相等本质一致
		list := []int{inserted, deleted, replaced}
		h := min(list) + 1
		dp[i][j] = h
		return h
	}
}

func min(list []int) int {
	m := math.MaxInt8
	for i := range list {
		if list[i] < m {
			m = list[i]
		}
	}
	return m
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

def minDistance(self, word1: str, word2: str) -> int:
    dp=[[-1 for i in range(len(word2)+1)] for i in range(len(word1)+1)]
    def help(i,j,word1,word2):
        if dp[i][j]!=-1:
            return dp[i][j]
        if i==0:
            return j
        if j==0:
            return i
        if word1[i-1]==word2[j-1]:
            h=help(i-1,j-1,word1,word2)
            dp[i][j]=h
            return h
        else:
            insert=help(i,j-1,word1,word2)
            delete=help(i-1,j,word1,word2)
            replace=help(i-1,j-1,word1,word2)
            l=[insert,delete,replace]
            h=min(l)+1
            dp[i][j]=h
            return h
    return help(len(word1),len(word2),word1,word2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22