编辑距离
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字符串。这便是带有
一行初始化的操作意义。
- 可能对字符串word1的头部进行1到word1.size()的删除，伴随其他增、改操作，以其变成word2字符串。这便是带有
那一列初始化的操作意义。
| 0 | r | o | s | |
|---|---|---|---|---|
| 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数组中状态由标有
的三个状态通过转移方程而来。
| 0 | * | r | o | s |
|---|---|---|---|---|
| * | 2 | 3 | ||
| h | ||||
| o | 2 | |||
| r | 3 | |||
| s | 4 | |||
| e | 5 |
状态转移方程为：
由上面的讲解。可知，的最小操作数是一，即由编辑操作中的修改操作而来的。也就是说，从状态转移方程的第三个式子而来。
由状态转移方程得到最终dp数组如下所示：
| 0 | r | o | s | |
|---|---|---|---|---|
| 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的角度来说，时间复杂度基本是, 没啥优化空间。
但是，由dp数组的使用上可以观察到，每次dp的时候，只是使用当前行与上一行而已。因此，dp数组只需要开dp[2][word2.size()]大小，复用该数组即可。即空间复杂度从降为
.
优化后的代码:
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()];
}
};
评测结果：
- 执行用时 : 36 ms, 在Edit Distance的C++提交中击败了10.46% 的用户
- 内存消耗 : 8.4 MB, 在Edit Distance的C++提交中击败了4.60% 的用户
此次优化，由于是复用dp数组，所以是由原来的变成
。但是从评测结果来说，可知内存的优化上变化不是很明显，说明评测数据量并不大。
网友评论