首页 > 代码库 > 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
分析:两个字符串的距离肯定不超过他们的长度之和(我们可以通过删除操作把两个串都转化为空串)。这两个字符串可以进行如下操作:
1.删除A串的第一个字符,然后计算A[2,...,lenA]和B[1,...,lenB]的距离;
2.删除B串的第一个字符,然后计算A[1,...,lenA]和B[2,...,lenB]的距离;
3.修改A串中的第一个字符为B串的第一个字符,然后计算A[2,...,lenA]和B[2,...,lenB]的距离;
4.修改B串中的第一个字符为A串的第一个字符,然后计算A[2,...,lenA]和B[2,...,lenB]的距离;
5.增加B串中的第一个字符为A串的第一个字符之前,然后计算A[1,...,lenA]和B[2,...,lenB]的距离;
6.增加A串中的第一个字符为B串的第一个字符之前,然后计算A[2,...,lenA]和B[1,...,lenB]的距离;
简而言之:
1.一步操作之后,再将A[2,...,lenA]和B[1,...,lenB]变成相同字符串;
2.一步操作之后,再将A[1,...,lenA]和B[2,...,lenB]变成相同字符串;
3.一步操作之后,再将A[2,...,lenA]和B[2,...,lenB]变成相同字符串;
具体情况参见:《编程之美》3.3计算字符串的相似度。
思路:递归方法,超时。
class Solution { public: int calStringDistance(string word1,int start1,int end1,string word2,int start2,int end2) { if(start1>end1) { if(start2>end2) return 0; else return end2-start2+1; } if(start2>end2) { if(start1>end1) return 0; else return end1-start1+1; } if(word1[start1]==word2[start2]) { return calStringDistance(word1,start1+1,end1,word2,start2+1,end2); } else { int t1=calStringDistance(word1,start1+1,end1,word2,start2,end2); int t2=calStringDistance(word1,start1,end1,word2,start2+1,end2); int t3=calStringDistance(word1,start1+1,end1,word2,start2+1,end2); return min(t1,min(t2,t3))+1; } } int minDistance(string word1, string word2) { calStringDistance(word1,0,word1.size()-1,word2,0,word2.size()-1); } };
思路二:动态规划来解题。定义一个二维数组dp来表示字符串word1和word2之间的距离。这个公式可以如下表示:
1.word1[i]==word2[i]时,dp[i][j]=dp[i-1][j-1];
2.其他状况下,增删修改如下公式:dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1);
class Solution { public: int minDistance(string word1, string word2) { int col=word1.size(); int row=word2.size(); vector<vector<int> > dp(col+1,vector<int>(row+1)); for(int i=0;i<=col;i++) { dp[i][0]=i; } for(int i=0;i<=row;i++) { dp[0][i]=i; } for(int i=1;i<=col;i++) { for(int j=1;j<=row;j++) { if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1]; else { dp[i][j]=min(min(dp[i][j-1]+1,dp[i-1][j-1]+1),dp[i-1][j]+1); } } } return dp[col][row]; } };