LeetCode72编辑距离

发表于 | 更新于 | 分类于 |
计算字符串之间的编辑距离

题目描述：

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

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

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

示例 1:

1
2
3
4
5
6
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

1
2
3
4
5
6
7
8
输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

解题思路：

是一个动态规划类问题。

关键是能想出或者画出如上的二维矩阵。如上矩阵中，

表示的是从word1[i]转换到word2[j]所需要的编辑距离。如上这样的动态规划矩阵中，要初始化第一行和第一列，类似于是一个空字符串转换到当前字符串所需要的编辑距离，就是等于当前字符串的长度。
1
2

在之后计算编辑距离时，如果word1[i]与word2[j]相等的话，那：```matrix[i][j] = matrix[i-1][j-1]``` ；如果word1[i] 不等于 word2[j] 的话，当前位置是从其之前行或者是列变化而来，需要操作数 +1 ，即：```min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1])+1

代码实现：

Python代码实现，GitHub地址为：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c72.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m = len(word1) + 1
        n = len(word2) + 1

        arr = [[0] * n for i in range(m)]

        row = [i for i in range(n)]
        arr[0] = row
        for i in range(m):
            arr[i][0] = i

        for i in range(len(word1)):
            for j in range(len(word2)):
                if word1[i] == word2[j]:
                    arr[i + 1][j + 1] = arr[i][j]
                else:
                    arr[i + 1][j + 1] = min(arr[i][j + 1], arr[i + 1][j], arr[i][j]) + 1

        return arr[m - 1][n - 1]