题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给两个字符串，求一个字符串到另一个字符串的最小编辑距离。所谓的编辑距离对一个字符串做插入、删除或更改一个字符算是一个单位的编辑距离。

思路分享

  • 求一个字符串（长为 n）到另一个字符串（长为 m）的最小编辑距离，比如求从 horse 到 ros 的编辑距离 l，可以视为 hors 到 ros 的距离 l+1（因为左边字符串最右边删去一个字符）以此类推，可以得到记忆化递归的写法。

  • 重点记录由两个一维数组优化到一个一维数组中的思路，由于这里的状态由其位置的左、左上、上三个地方决定，所以必须从左向右遍历，如果直接这么做，会丢失坐上的数据，所以需要额外一个变量记录左上位置的数据，并及时更新。

代码解答（强烈建议自行解答后再看）

  • 参考题解
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
55
56
57
58
59
60
61
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 优化成一维数组
        n, m = len(word1), len(word2)
        f = list(range(m+1))
        # print(f)
        for i, x in enumerate(word1):
            pre = f[0]
            f[0] += 1
            for j, y in enumerate(word2):
                tmp = f[j+1]
                f[j+1] = pre if x == y else min(f[j+1], f[j], pre) + 1
                pre = tmp
        
        return f[m]


        # 优化成两个一维数组
        # n, m = len(word1), len(word2)
        # f = [list(range(m+1)), [0] * (m+1)]
        # # print(f)
        # for i, x in enumerate(word1):
        #     f[(i+1)%2][0] = i+1
        #     for j, y in enumerate(word2):
        #         f[(i+1)%2][j+1] = f[i%2][j] if x == y else min(f[i%2][j+1], f[(i+1)%2][j], f[i%2][j]) + 1
                    
        # # print(f)
        # return f[n%2][m]

        # 翻译成递推
        # n, m = len(word1), len(word2)
        # f = [[0] * (m+1) for _ in range(n+1)]
        # for i in range(n+1):
        #     f[i][0] = i
        # for i in range(m+1):
        #     f[0][i] = i
        # for i, x in enumerate(word1):
        #     for j, y in enumerate(word2):
        #         if x == y:
        #             f[i+1][j+1] = f[i][j]
        #         else:
        #             f[i+1][j+1] = min(f[i][j+1], f[i+1][j], f[i][j]) + 1
        # # print(f)
        # return f[n][m]

        # 记忆化递归
        # n, m = len(word1), len(word2)
        # @cache
        # def dfs(i:int, j:int) -> int:
        #     if i < 0:
        #         # 插入 j+1
        #         return j+1
        #     if j < 0:
        #         # 删除 i+1
        #         return i+1
        #     # 相同字符就不用加操作数
        #     if word1[i] == word2[j]:
        #         return dfs(i-1, j-1)
        #     # 分别是删除和替换，插入
        #     return min(dfs(i-1, j), dfs(i-1, j-1), dfs(i, j-1)) + 1
        # return dfs(n-1, m-1)