LeetCode Python - 72. 编辑距离

题目描述

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

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

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2：

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

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

解法

我们定义 f[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所使用的最少操作数。初始时 f[i][0]=i, f[0][j]=j。其中 i∈[1,m],j∈[0,n]。

考虑 f[i][j]：

如果 word1[i−1]=word2[j−1]，那么我们只需要考虑将 word1 的前 i−1 个字符转换成 word2 的前 j−1
个字符所使用的最少操作数，因此 f[i][j]=f[i−1][j−1]；
否则，我们可以考虑插入、删除、替换操作，那么 f[i][j]=min(f[i−1][j],f[i][j−1],f[i−1][j−1])+1。

综上，我们可以得到状态转移方程：

f[i][j]={ i,if j=0 j,if i=0 f[i−1][j−1],if word1[i−1]=word2[j−1] min(f[i−1][j],f[i][j−1],f[i−1][j−1])+1,otherwise

最后，我们返回 f[m][n] 即可。

时间复杂度 O(m×n)，空间复杂度 O(m×n)。其中 m 和 n 分别是 word1 和 word2 的长度

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m, n = len(word1), len(word2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for j in range(1, n + 1):
            f[0][j] = j
        for i, a in enumerate(word1, 1):
            f[i][0] = i
            for j, b in enumerate(word2, 1):
                if a == b:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1
        return f[m][n]