Problem
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
题意
对于给定两个单词word1和word2，你可以对word1进行以下3种操作：
a） 插入一个字母
b） 删除一个字母
c） 替换一个字母
请计算将word1变换成word2的最少操作数。
分析
此题是一个非常典型动态规划问题，里面涉及到一个概念（即本题的题目）：编辑距离。
编辑距离
两个字符串的各种对齐所可能具有的最小代价。
即，它可以被视为将一个字符串变换为另一个字符串所需最小编辑操作，包括插入、删除以及字符替换的次数。
用动态规划思想解决
如何划分子问题
- 有两个字符串x[1...n]，y[1...m]
- 考虑两个字符串的长度各自为i和j的前缀x[1...i]，y[1...j]
- 对于x[i]和y[j]的最佳对齐（最佳对齐是指，为得到全局最优解而取的局部最优解），有以下可能的三种情况：
三种对齐方式（- 代表一个空隙）
对空格及编辑代价的解释
当两个字符串不相同时，想要对齐它们，可以写成如下形式（以SNOWY和SUNNY为例）：
代价为3
或
代价为5
其中，-表示一个空隙，对齐时，可以将它随意插入到每个字符串中。对于一种对齐方式，其代价是指上下字符串对应字母不相同的列数。而编辑距离是指两个字符串的各种对齐所可能具有的最小代价。
利用二维矩阵
以exponential和polynomial为例，结合我们上面谈到的对两个字符串中的两个字符进行对齐，算出其代价，可得到如下的二维矩阵：
其中，(i, j) = min(1 + (i - 1, j), 1 + (i, j - 1), diff(w1[i], w2[j]) + (i - 1, j - 1))
该算法的伪代码：
伪代码
参考资料
《算法概论》/《Algorithm》 - Sanjoy Dasgupta著；
第六章 动态规划：6.3 编辑距离
Code
//Runtime: 12ms
class Solution {
public:
int diff(char a, char b){
return !(a == b);
}
int min(const int& a, const int& b, const int& c){
int tmp = a < b ? a : b;
return (tmp < c ? tmp : c);
}
int minDistance(string word1, string word2) {
if(word1.size() == 0 && word2.size() == 0)
return 0;
if (word1.size() == 0 && word2.size() != 0)
return word2.size();
if (word2.size() == 0 && word1.size() != 0)
return word1.size();
vector<vector<int>> matrix;
matrix.resize(word1.size() + 1);
for (int i = 0; i < word1.size(); i++)
matrix[i].resize(word2.size() + 1);
matrix[0][0] = 0;
for (int i = 1; i < word1.size() + 1; i++)
matrix[i][0] = matrix[i - 1][0] + 1;
for (int j = 1; j < word2.size() + 1; j++)
matrix[0][j] = matrix[0][j - 1] + 1;
for (int i = 1; i < word1.size() + 1; i++)
for (int j = 1; j < word2.size() + 1; j++){
matrix[i][j] = min(1 + matrix[i - 1][j],
1 + matrix[i][j - 1],
diff(word1[i - 1], word2[j - 1]) + matrix[i - 1][j - 1]);
}
return matrix[word1.size()][word2.size()];
}
};
