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]
