编辑距离（edit distance）

编辑距离

LeetCode 72. 编辑距离

概念

编辑距离，是指将字符串word1通过替换、删除、增加字符的操作，变成字符串word2的最小次数。

用途

编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。

DNA也可以用A、C 、G和T组成的字符串表示，因此编辑距离也可以用在生物信息学中，判断两个DNA的相似程度。

Unix下的diff及patch命令也是利用编辑距离来进行文本编辑对比的例子。

动态规划简介

动态规划，是指当前状态是由之前的状态通过转移方程（即某一种或几种方跃迁方式）得到的。也就是说，通过设法利用之前所存储的状态（一般是一维、二维、三维数组等存放状态），来更新现有的状态。最后，依次迭代，获得最终状态。

这种类型题是用了动态规划的做法来做。

题目描述

给定两个单词 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')

初始化dp（重要）

以示例一为例，对二维数组dp进行初始化。dp数组的大小为dp[word1.size()+1][word2.size()+1]。数组大小原因如下：

可能要对字符串word1的头部插入1到word2.size()个字符，使其变成word2字符串。这便是带有 $\color{green}{*}$ 一行初始化的操作意义。
可能对字符串word1的头部进行1到word1.size()的删除，伴随其他增、改操作，以其变成word2字符串。这便是带有 $\color{red}{*}$ 那一列初始化的操作意义。

0	$\color{red}{*}$	r	o	s
$\color{green}{*}$	0	1	2	3
h	1
o	2
r	3
s	4
e	5

状态转移方程（核心）

当前状态，可由上一个状态A加上增加一个字符、上一个状态B修改（或不修改）一个字符或上一个状态C删除一个字符得到。每个状态包含着该状态最小操作步数。

如：

h o r s e

r o s

中， h与r的编辑操作中，显然是将h修改成r为最小操作数（一个操作数）。而不是将h前面加上r，再删除h（两个操作数）或是删除h，再加上r（两个操作数）。

对应到dp数组中，即dp数组中 $\color{red}{A}$ 状态由标有 $\color{green}{颜色}$ 的三个状态通过转移方程而来。

0	*	r	o	s
*	$\color{green}{0}$	$\color{green}{1}$	2	3
h	$\color{green}{1}$	$\color{red}{A}$
o	2
r	3
s	4
e	5

状态转移方程为：

$dp[i][j] = min\left\{ \begin{array} \\ dp[i][j-1]+1, add\ character; \\ dp[i-1][j]+1, delete\ character; \\ dp[i-1][j-1] + word1[i]==word2[j], \\ change\ if\ it's\ needed. \\ \end{array}\right.$

由上面的讲解。可知， $\color{red}{A}$ 的最小操作数是一，即由编辑操作中的修改操作而来的。也就是说，从状态转移方程的第三个式子而来。

由状态转移方程得到最终dp数组如下所示：

0	$\color{red}{*}$	r	o	s
$\color{green}{*}$	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

实现代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        if(word1.empty() || word2.empty()) {
            return max(word1.size(), word2.size());
        }
        
        // 建立dp数组。
        int dp[word1.size()+1][word2.size()+1];
        
        // 初始化dp数组，为删除1到word1.size（）个字符。
        for(int i=0; i <= word1.size(); ++i) {
            dp[i][0] = i;
        }
        
        // 初始化dp数组，为增加1到word2.size（）个字符。
        for(int i=0; i <= word2.size(); ++i) {
            dp[0][i] = i;
        }
        
        // 进行dp操作，由上述的状态转移方程迁移而来。
        for(int i=1; i <= word1.size(); ++i) {
            for(int j=1; j <= word2.size(); ++j) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1));
            }
        }
        
        // 返回dp的最终结果。
        return dp[word1.size()][word2.size()];
    }
};

评测结果：

执行用时 : 20 ms, 在Edit Distance的C++提交中击败了18.77% 的用户
内存消耗 : 9.4 MB, 在Edit Distance的C++提交中击败了4.60% 的用户

代码优化

从dp的角度来说，时间复杂度基本是 $O(N^2)$ , 没啥优化空间。

但是，由dp数组的使用上可以观察到，每次dp的时候，只是使用当前行与上一行而已。因此，dp数组只需要开dp[2][word2.size()]大小，复用该数组即可。即空间复杂度从 $O(N^2)$ 降为 $O(N)$ .

优化后的代码:

class Solution {
public:
    int minDistance(string word1, string word2) {
        if(word1.empty() || word2.empty()) {
            return max(word1.size(), word2.size());
        }
        
        // 建立dp数组。
        int dp[2][word2.size()+1];
                
        // 初始化dp数组，为增加1到word2.size（）个字符。
        for(int i=0; i <= word2.size(); ++i) {
            dp[0][i] = i;
        }
        
        // 进行dp操作，由上述的状态转移方程迁移而来。
        // 增加两个变量，用来标记dp数组的操作方式。
        int last_index = 0;
        int current_index = 1;
        for(int i=1; i <= word1.size(); ++i) {
            // 初始化dp数组，表示删除word字符的操作数
            dp[current_index][0] = i;
            
            // 通过状态方程进行跃迁
            for(int j=1; j <= word2.size(); ++j) {
                dp[current_index][j] = min(dp[last_index][j], dp[current_index][j-1]) + 1;
                dp[current_index][j] = min(dp[current_index][j], dp[last_index][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1));
            }
            
            // 交换这两个变量，复用数组
            swap(last_index, current_index);
        }
        
        // 返回dp的最终结果。
        return dp[last_index][word2.size()];
    }
};