164 - 72 编辑距离

题目

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

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

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

示例 1:

输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution" 输出: 5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

解答

https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-mian-shi-ti-xiang-jie-by-labuladong/

这个大佬巨牛批。。这个算法还能联系现实。。

关键是，一般题解，最多就解释一下这个题解，思路是什么。但是这个大佬就从头告诉你，怎么从0开始搞出类似的题解。

“授人渔”的大佬。

那么来整理下思路：暴力=>带备忘录（自顶向下）=>动态规划（自底向上）

暴力法

• 两个字符串的动态规划，一般用两个指针，从后往前走

• 具体到这个问题，有几个边界情况base case：

• 如果两指针对应的字母相等，那么直接跳过

• 如果一个指针指到头了i==-1，那么另一个指针就需要吧剩下的内容全部插入

我们只负责计算编辑距离，并不实际上替换掉具体的值。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        def dp(i, j):  # dp含义：返回word1[0:i]和word2[0:j]的最小编辑距离
              # 边界情况
            if i == -1:  # 如果i指到头了，那么编辑距离就是j还指了几位，都要插入进去
                return j+1  
            if j == -1:
                return i+1

            if word1[i] == word2[j]:
                return dp(i-1, j-1) # 如果一样，就跳过。即不加上编辑距离
            else:
                return min(   # 插入、替换、删除，都是要花费编辑距离的，都要加一
                    dp(i, j-1)+1,  # 插入
                    dp(i-1, j)+1,  # 删除
                    dp(i-1, j-1)+1 # 替换
                )

        return dp(len(word1)-1, len(word2)-1)

当然是超时了了

备忘录

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        memo = dict()

        def dp(i, j):
            if (i, j)in memo:
                return memo[(i, j)]
            if i == -1:
                return j+1
            if j == -1:
                return i+1
            if word1[i] == word2[j]:
                memo[(i, j)] = dp(i-1, j-1)
            else:
                memo[(i, j)] = min(
                    dp(i, j-1)+1,
                    dp(i-1, j)+1,
                    dp(i-1, j-1)+1
                )
            return memo[(i, j)]

        return dp(len(word1)-1, len(word2)-1)

Runtime: 84 ms, faster than 98.37% of Python3 online submissions for Edit Distance.

Memory Usage: 15.1 MB, less than 92.31% of Python3 online submissions for Edit Distance.