Edit-Distance

¶开始 Starting

Edit Distance

Algorithm by Sanjoy Dasgupta

p.175

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

¶题目 Question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

¶想法 Thinking

我们先想当最好情况下的alignment between $x[1:i]$ 和 $y[1:j]$ : 有三种情况：

x[1:i-1] and y[1:j] remains	x[1:i] and y[1:j-1] remains	x[1:i-1] and y[1:j-1] remains
x[i]	—	x[i]
—	y[j]	y[j]

前两者情况 Cost 都为 1， 最后一种情况 如果相等则cost 为0，otherwise 为1

In short, we have expressed E(i, j) in terms of three smaller subproblems E(i − 1, j), E(i, j − 1), E(i − 1, j − 1).

因为无从知晓哪种情况是最优，做一个min：

$E(i, j) = min$ {$1 + E(i − 1, j), 1 + E(i, j − 1), diff(i, j) + E(i − 1, j − 1)$}

也就是说，我们的problem 已经可以转化成多个sub-problem，然后 optimal 是由其中最小的组成。 我们可以用matrix 把所有可能的 (i,j) 组合表示出来

我们可以同时记录path， 这样到最后结果的path就能被记录下来。往下走是delete （第一种情况） ，往右走是insert （第二种情况）, 斜着走是 match or substitution

¶算法 Algorithm

//Psedo-code
for i = 0, 1, 2, . . . , m:
	E(i, 0) = i
for j = 1, 2, . . . , n:
	E(0, j) = j
for i = 1, 2, . . . , m:
	for j = 1, 2, . . . , n:
		E(i, j) = min{E(i − 1, j) + 1, E(i, j − 1) + 1, E(i − 1, j − 1) + 					diff(i, j)}
return E(m, n)

前面两个for loop initialize 这个matrix， 第三个 for loop 遍历所有的格子（row by row）

¶运行时间 Run-time

每次填写格子常数时间，所以共O(mn)

¶反思 Introspection

😂看书比上课管用