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) 组合表示出来

image-20210414172023798

image-20210414173117110

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

算法 Algorithm

1
2
3
4
5
6
7
8
9
10
//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

:joy:看书比上课管用


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!