莱文斯顿距离（python版）

莱文斯顿距离（python版）

莱文斯顿距离（python版）

• leetcode No.72

leetcode No.72

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例：

输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

首先，使用动态规划思想，首先创建一个二维数组subset，长度为len(word2) + 1，宽度为len(word1) + 1，二维数组中的每一个位置用来记录每一步的最小距离。其中第一行表示word1为空字符串，并依次从空字符串变成word2（依次插入）；第一列表示word2为空字符串，并依次从word1变成空字符串（依次删除）。根据上面已知条件对数组进行初始化赋值。

然后，按照以下条件依次对二位数组中的每个位置(row, column)进行赋值：
（1）当word1[row - 1] != word2[column - 1]时，subset[row][column] 的取值等于该位置左方、上方、左上方距离为1的位置的最小值加1，即
subset[row][column] = min(subset[row - 1][column - 1], subset[row - 1][column], subset[row][column - 1]) + 1
(2)当word1[row - 1] == word2[column - 1]时，subset[row][column] 的取值等于该位置左上方的值，可以理解为由于字符相等编辑距离无需加1操作，即当前最小距离等于同时删除word1以及word2的当前字符的最小距离（左上方距离为1处的值）。

下面解释一下二维数组中的移动方向分别表示的意义：

1. ↓ 表示删除word1的当前字符操作（距离+1）
2. → 表示插入word2的当前字符操作（距离+1）
3. ↘ 表示将当前word1的字符替换为word2的当前字符（距离+1）
4. ↖ 可以理解为当前word2的字符与当前word1的字符相同时，同时将这两个字符删除（距离维持不变）

举例，word1=kitten，word2=sitting

word1与word2最小编辑距离即为二维数组最右下方的值：
subset[-1][-1] == 3

代码（python）：

def minDistance(word1, word2):length1 = len(word1) + 1length2 = len(word2) + 1subset = [[0] * length2 for i in range(length1)]for i in range(length2):subset[0][i] = ifor j in range(length1):subset[j][0] = jfor row in range(1, length1):for column in range(1, length2):if word1[row - 1] != word2[column - 1]:subset[row][column] = min(subset[row - 1][column - 1],subset[row - 1][column], subset[row][column - 1]) + 1else:subset[row][column] = subset[row - 1][column - 1]return subset[-1][-1]

测试：

word1, word2 = "horse", "ros"
print(minDistance(word1, word2))

输出：

3