Skip to content

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]


回到顶部