072 edit distance
72. Edit Distance
题目: https://leetcode.com/problems/edit-distance/
难度:
Hard
可以做的操作：
- 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
用wikipedia上的伪码改造
function LevenshteinDistance(char s[1..m], char t[1..n]):
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t
// note that d has (m+1)*(n+1) values
declare int d[0..m, 0..n]
set each element in d to zero
// source prefixes can be transformed into empty string by
// dropping all characters
for i from 1 to m:
d[i, 0] := i
// target prefixes can be reached from empty source prefix
// by inserting every character
for j from 1 to n:
d[0, j] := j
for j from 1 to n:
for i from 1 to m:
if s[i] = t[j]:
substitutionCost := 0
else:
substitutionCost := 1
d[i, j] := minimum(d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + substitutionCost) // substitution
return d[m, n]
对应的例子表格图
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))
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]
