Leetcode-72.编辑距离★

题目来源：https://leetcode-cn.com/problems/edit-distance/

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

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

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

示例 1：

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

解法：动态规划

对两个单词A和B，可以执行的操作共有六种，其中有三种是重复的：

对单词A删除一个字符＝ 对单词B添加一个字符
对单词A添加一个字符 ＝对单词B删除一个字符
对单词A替换一个字符 ＝对单词B替换一个字符（因为替换的结果是A和B一定会更加接近，所以其实是等价的）

设状态 $dp[i][j]$ 表示单词A的前i个字符和单词B的前j个字符之间的编辑距离，则有以下推理：

对单词A添加一个字符： $dp[i][j] = dp[i-1][j] + 1$
对单词B添加一个字符： $dp[i][j] = dp[i][j-1] + 1$
对单词A修改字符： $dp[i-1][j-1]$ 表示A的前（i-1）个字符和B的前（j-1）个字符之间的编辑距离，那么对于A的下一个（第i个）字符和B的下一个（第j个）字符，如果A[i] == B[j]，那么什么也不用做，有： $dp[i][j] = dp[i-1][j-1]$ 。否则，需要增加一次修改操作，所以有： $dp[i][j] = dp[i-1][j-1]+1$

汇总所有情况，得状态转移方程为：

$dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])\begin{matrix} & & \end{matrix}if A[i] == B[j]$ $dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, dp[i][j-1]+1)\begin{matrix} & & \end{matrix}else$

考虑状态初始化：

当A[i]为空串时，编辑距离等于B[j]的长度： $dp[0][j] = j$
当B[j]为空字符时，编辑距离等于A[i]的长度： $dp[i][0] = i$

考虑特殊情况：

A和B有一个为空时，编辑距离等于不为空的字符串的长度

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n = len(word1)
        m = len(word2)
        if n * m == 0:         # 特殊情况
            return n or m
        dp = [[0] * (m+1) for _ in range(n+1)]
        for i in range(n+1):      # 边界情况
            dp[i][0] = i
        for j in range(m+1):
            dp[0][j] = j
        for i in range(1, n+1):         # 一般情况，状态转移
            for j in range(1, m+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j] + 1, dp[i][j-1] + 1)
                else:
                    dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
        return dp[n][m]

参考：

https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/