难度: Hard
原题连接
内容描述
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
思路 1 - 时间复杂度: O(len(word1)len(word2))- 空间复杂度: O(len(word1)len(word2))****
可以做的操作：
- insert
- delete
- replace
动归典型，原来也是有wikipedia page的算法
https://en.wikipedia.org/wiki/Edit_distance#Common_algorithm
https://en.wikipedia.org/wiki/Levenshtein_distance
看wikipedia 这解释
/ max(i,j) if min(i,j) = 0
/ dp[i-1][j] + 1 word1[i]不在word2[0...j]中,所以删除
dp[i][j] - min -- dp[i][j-1] + 1 insertion
\ dp[i-1][j-1] + 1/0 word[i]与word[j]是否相等
上面的就不用解释了，min分别对应：删除、插入、以及替代（1/0取决 word1[i] == word2[j] ），反正也是tabular类型，画表来解决问题。
简单说，就是这样：
1.delete：dp[i-1][j] + 1 —— 保留了从 word1[0:i-1] 转变到 word2[0:j] 的最优操作次数，因为我们的 word1 的 0~i-1 已经能够转变到 word2 了， 所以我们就直接把 word1 中的最后一个字符删除掉就行了。所以就需要额外进行一个 删除 操作。
2.insert：dp[i][j-1] + 1 —— 保留了从 word1[0:i] 转变到 word2[0:j-1] 的最优操作次数，因为我们的 word1 的 0~i 只能转变到 word2 的倒数第二位，所以我们就直接在 word1 的末尾添加一个与 word2 的最后一个字符相同的字符就可以了。所以就需要额外进行一个 插入 操作。
3.replace：dp[i-1][j-1] + 1 —— 保留了从 word1[0:i-1] 转变到 word2[0:j-1] 的最优操作次数，因为我们的 word1 的 0~i-1 只能转变到 word2 的倒数第二位，而 word1 的最后一位与 word2 的最后一位是不同的，所以现在的情况只需要额外的一个 替换 操作即可。
无论我们选取上面 3 中操作的哪种操作，我们选其中最小的值就可以了。
参考链接：http://www.cnblogs.com/pandora/archive/2009/12/20/levenshtein_distance.html
要始终明确一点，dp[i][j]的含义是使得word1的前i字符子串与word2的前j字符子串相等所需要的操作数，这也是为什么我们需要在初始化dp矩阵时需要行列数均加上1
对应的例子表格图
k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
AC代码
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if len(word1) == 0 or len(word2) == 0: # corner cases
return max(len(word1), len(word2))
# 这里第一行第一列初始值一定要为i+j，因为当另一个单词为空的时候很明显至少需要i或者j次edit
dp = [[i+j for j in range(len(word2)+1)] for i in range(len(word1)+1)]
for i in range(1, len(word1)+1):
for j in range(1, len(word2)+1):
tmp_dist = 0 if word1[i-1] == word2[j-1] else 1
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+tmp_dist)
return dp[-1][-1]或者你愿意麻烦，可以这样初始化dp矩阵
dp = [[0 for j in range(len(word2)+1)] for i in range(len(word1)+1)]
dp[0] = [i for i in range(len(word2)+1)]
for i in range(len(word1)+1):
dp[i][0] = i