莱文斯坦距离

IMG_0694.png

Leetcode 583.两个字符串的删除操作
略微修改了莱文斯坦距离公式，题目中只有删除操作，无替换 所以

 由
 # 替换，插入，删除
 levab[i][j] = min(levab[i - 1][j - 1] + 1, levab[i][j - 1] + 1, levab[i - 1][j] + 1)
 ----->
 levab[i][j] = min(levab[i - 1][j - 1] + 2, levab[i][j - 1] + 1, levab[i - 1][j] + 1)

代码:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        levab = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
        # 1.计算空字符串到各字符的莱文斯坦距离
        for j in range(len(word2) + 1):
            for i in range(len(word1) + 1):
                if min(i, j) == 0:
                    levab[i][j] = max(i, j)
                    # 如果ai = bj 则不做任何操作 ，莱文斯坦距离等于上一个子串的莱文斯坦距离
                elif word2[j-1] == word1[i-1]:
                    levab[i][j]=levab[i - 1][j - 1]
                else:
                    # 替换，插入，删除
                    levab[i][j] = min(levab[i - 1][j - 1] + 2, levab[i][j - 1] + 1, levab[i - 1][j] + 1)

        return levab[-1][-1]