动态规划专题 (III)：Leetcode 72 编辑距离

Leetcode 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')

题解

编辑距离是最小的改变次数这句话是这个题目的核心

整个递归式是这样的：（分三种情况）对于当前字母 word1[i]， word2[j] 来说。

如果当前两个字母相匹配，那这个字符就不会改变，因此对这个问题就满足：
$Edit(word1, word2)=Edit(word1[0 : i-1], word2[0 : i-1])$
若两个字母不匹配，那这个字符就会产生改变，但是改变有三种方式：
1. word1 插入一个元素，对应的：
  $Edit(word1, word2)=Edit(word1[0 : i-1], word2[0 : i])+1$
2. word2 插入一个元素
  $Edit(word1, word2)=Edit(word1[0 : i], word2[0 : i-1])+1$
3. 改变一个元素
  $Edit(word1, word2)=Edit(word1[0 : i-1], word2[0 : i-1])+1$

之前提到了说，编辑距离是最小的改变次数因此这个问题的核心就是在字符不相同的时候，找以上三种情况的最小值。

因此转化为递归式就有了网上经常能看到的转移方程。

$begin{cases} dp[i][j] = dp[i-1][j-1] & text{if word1[i]=word2[j]}\ dp[i][j] = min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]}+1 & text{if word1[i] $ne$ word2[j]} end{cases}$

对于边界情况，左上角一定是0，将这个字符串扩充为：

word1 = " " + word1
word2 = " " + word2

假设这两个字符串为 "horse"，"ros" 那这个矩阵为：

$left[begin{matrix} ddots&"text{ }"&h&o&r&s&e\ "text{ }"&0\ r\ o\ s end{matrix}right]$

因为 word1 和 word2 的第 i 第 j 不可能是 " "，因此根据上面的式子，可以推出：

$dp[i][j]= min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]}$

因此这个矩阵初始化为：

$left[begin{matrix} ddots&"text{ }"&h&o&r&s&e\ "text{ }"&0&1&2&3&4&5\ r&1\ o&2\ s&3\ end{matrix}right]$

可以发现，初始化横纵第一列、行一定是一个连续从 0 递增的序列。因此按照转移方程，最终结果在矩阵的右下角得到

整个代码如下：

class Solution(object):
    def minDistance(self, word1, word2):
        word1 = " " + word1
        word2 = " " + word2
        matrix = [[None for j in word2] for i in word1]
        n = len(word1)
        m = len(word2)
        # Initialize
        for i in range(0, n):
            matrix[i][0] = i
        for j in range(0, m):
            matrix[0][j] = j
        for i in range(1, n):
            for j in range(1, m):
                if word1[i] == word2[j]:
                    matrix[i][j] = matrix[i-1][j-1]
                else:
                    # 分别为：替换一个，word1插入一个，word2插入一个
                    matrix[i][j] = min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]) + 1
        return matrix[-1][-1]