[NLP] 2.3 编辑距离和对齐 （Edit Distance and Alignment）

获得两个strings的距离，是非常有价值的事情。
你可以用这个进行单词的修正，例如你在office里面输入了单词graffe，然后软件帮你自动搜索最近的单词，类似graf，graft等等。
对于基因编辑来说，也非常有帮助。我们都知道基因由AGCT序列组合而成，它们可以被视为文本，然后查找最近的基因序列。

Edit Distance 编辑距离

我们可以使用编辑距离，表征两个strings的关系，其中『编辑』包含了如下操作：

• 插入
• 删除
• 替换
  使用这三个操作，能够把一个字符变成另外一个，最少使用多少次，那么就是编辑距离。

如何获取最小编辑距离，其实就是一道leetcode困难题的事儿:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # x轴是word2，y是word1，+1是初始位置
        dp = [[0]* (len(word2)+1) for _ in range(len(word1)+1)]
        # 初始空位置，如果想要成为word1，需要不停的insert操作
        for i in range(len(dp)):
            dp[i][0] = i
        # 同理，如果想要成为word2，也要不停的insert
        for j in range(len(dp[0])):
            dp[0][j] = j
        # 从(1,1)开始迭代
        for i in range(1,len(dp)):
            for j in range(1,len(dp[i])):
                # 取左，上，左上的最小值，然后进行一个操作（+1）
                dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
                # 如果两个字符相同，那不用变，直接取左上的操作数
                if word1[i-1] == word2[j-1]:
                    dp[i][j] =dp[i-1][j-1]
        return dp[-1][-1]

直接看题解即可：
https://leetcode-cn.com/problems/edit-distance/solution/edit-distance-by-ikaruga/