Solve

Leetcode 72 - Edit Distance

我自打工作后从来没有在工作中用到过竞赛算法，直到我参与了编译器开发后一些辅助性质的工作中使上了动态规划，其一就是针对某种字符串做相似度检验时随手写了个LCS，另外一个就是编辑距离了。

题目解答

思想跟LCS很想，只不过要处理下述三种情况，具体参考程序源码：

  1. Insert a character
  2. Delete a character
  3. Replace a character

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if not word1 or not word2:
            return len(word1) + len(word2)
        
        dp = [[-1 for _ in range(len(word2))] for _ in range(len(word1))]
        
        for i in range(len(word1)):
            for j in range(len(word2)):
                a1 = dp[i - 1][j - 1] + (word1[i] != word2[j]) \
                    if i > 0 and j > 0 else i + j + (word1[i] != word2[j])
                a2 = dp[i - 1][j] + 1 if i > 0 else j + 2
                a3 = dp[i][j - 1] + 1 if j > 0 else i + 2
                dp[i][j] = min(a1, a2, a3) 
        
        return dp[len(word1) - 1][len(word2) - 1]