25
08/2015
[LeetCode] Edit Distance
Edit Distance
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
解题思路：
这道题计算两个文本的编辑距离。用动态规划的思想做。d[i][j]表示从字符串a(0..i)变换成b(0...j)的最小变换次数。则有：
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
if(m == 0 || n == 0){
return max(m, n);
}
vector<vector<int>> d(m + 1, vector<int>(n + 1, 0));
for(int i = 0; i<=n; i++){
d[0][i] = i;
}
for(int i=0; i<=m; i++){
d[i][0] = i;
}
for(int i = 1; i<=m; i++){
for(int j = 1; j<=n; j++){
if(word1[i-1] == word2[j-1]){
d[i][j] = d[i-1][j-1];
}else{
d[i][j] = min( min(d[i][j-1], d[i-1][j]), d[i-1][j-1] ) + 1;
}
}
}
return d[m][n];
}
};上述代码的时间复杂度和空间复杂度均为O(n^2)。可以将代码改成O(n)的空间复杂度。
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
if(m == 0 || n == 0){
return max(m, n);
}
vector<int> d(n + 1, 0);
for(int i = 0; i<=n; i++){
d[i] = i;
}
for(int i = 1; i<=m; i++){
int left = i;
int leftUp = i - 1;
for(int j = 1; j<=n; j++){
int up = d[j];
int newVal;
if(word1[i-1] == word2[j-1]){
newVal = leftUp;
}else{
newVal = min(min(left, up), leftUp) + 1;
}
leftUp = d[j];
d[j] = newVal;
left = d[j];
}
}
return d[n];
}
};转载请注明：康瑞部落 » [LeetCode] Edit Distance
0 条评论