72. 编辑距离 [hard]

https://leetcode-cn.com/problems/edit-distance/

编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。

给你两个单词 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')

通过次数63,034 | 提交次数106,252

First Try

2020-06-18

动态规划其实有点无脑流，反正不管过程中有多少种可能，就考虑从上一个状态到这个状态之间的可能，并且认为上一种状态已经被确定，同时更重要的是认为从上一个状态的最佳到这个状态的最佳就是整体的最佳。

对我而言比较难以说服自己的是，前一个状态的最佳，叠加前一个状态到当前状态的最佳，结果就是整体的最佳，还没法完全信服。毕竟局部最优并不代表整体最优，但是连续的局部递推最优，是不是就代表着整体最优呢？哪里来个详细的讨论。。

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        太难了吧，一眼看上去毫无办法
        偷瞄了一眼题解的开头，有了点思路

        - 两个单词之间互相转换，与一个单词转换为另一个单词，是互相等价的
        - 三种操作让人有点难以遍历，其实本质上插入一个字符和删除一个字符是一样的(无非是w1和w2之间的差别)， 替换一个字符则在w1和w2之间也是一样的
        - w1为空，转换距离为len(w2)
        - 假设w1在(0, i)的位置需要k次转换到w2(0, j), 则w1(0, i)到w2(0, j+1)需要额外一次转换(k+1)
          从w1在(0, i+1)转换到w2(0, j)， 则也是需要额外一次转换
         （重点是两个字符串都要完全匹配，因此没法跳过前面无关的内容，只能从0开始）
         - 这样一路往前推，直接到(len(w1), len(w2))就可以了，一路无脑往前推真是无敌
         - 好像忘了一个问题，horse和ors的匹配如何处理，从头走怎么能知道跳过前面1个字符和最后1个字符？
         （但是i,j遍历的操作，可以假设i在任意位置开始，j也在任意位置开始，应该是被遍历到了？
         - 竟然一次就通过了，细节我都还没完全想明白。。
        """
        n1, n2 = len(word1), len(word2)
        cache = [["" for j in range(n2+1)] for i in range(n1 + 1)]
        for i in range(n1 + 1):
            cache[i][0] = i
        for j in range(n2 + 1):
            cache[0][j] = j
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):              
                # just add from word 2
                choice_one = cache[i][j - 1] + 1
                # add from world 1
                choice_two = cache[i-1][j] + 1 
                # swift the last word
                swift = 0 if word1[i-1] == word2[j-1] else 1
                choice_three = cache[i-1][j-1] + swift
                cache[i][j] = min(choice_one, choice_two, choice_three)
        
        return cache[n1][n2]

执行用时 :168 ms, 在所有 Python 提交中击败了32.48%的用户
内存消耗 :15.9 MB, 在所有 Python 提交中击败了50.00%的用户

72. 编辑距离 [hard]​

First Try​

72. 编辑距离 [hard]

First Try