题目：

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

给定任意两个字符串，写出一个算法计算它们的编辑距离，如果成功计算出字符串的距离，否则返回-1；

 eg：

字符串A:abcdefg

字符串B: abcdef

通过增加或是删掉字符”g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

题解： 

这道题我们采用动态规划的方法，即定义一个dp[ i ][ j ],存储第一个字符串前i个字符与后一个字符串前j个字符相等时，最小的编辑距离。

如果两个字符串当前的两个字符相等，即第i个字符与第j个字符相等，那么dp[ i ][ j ] = dp [ i-1 ] [ j-1 ];

如果两个字符串当前的两个字符不相等，我们有三种操作增加，删除，更改；

当我们采用增加操作的时候，

在第一个字符串前增加 dp[ i ][ j ]=dp[ i -1 ][ j ]+1

在第二个字符串前增加 dp[ i ][ j ]=dp[ i ][ j-1 ]+1

当我们采用修改这个操作的时候： dp[ i ][ j ]=dp[ i-1 ][ j-1 ]+1;

当我们采用删除操作的时候

在第一个字符串前删除 dp[ i ][ j ]=dp[ i  ][ j-1 ]+1  即第i+1个字符与第j个字符比较

在第二个字符串前删除 dp[ i ][ j ]=dp[ i -1 ][ j ]+1  即第i个字符与第j+1个字符比较

代码实现：

int calStringDistance(string& str1,string& str2) { if(str1.empty()&&str2.empty()) return 0; if(str1.empty()) return str2.size(); else if(str2.empty()) return str1.size(); int len1=str1.size(); int len2=str2.size(); vector<vector<int>> dp(len1+1,vector<int >(len2+1)); //倘若让一个空串与有i个字符的字符串相等，编辑最少的时候，就是增加i个相同字符 for(int i=0;i<len1+1;++i) { dp[i][0]=i; } for(int j=0;j<len2+1;++j) { dp[0][j]=j; } for(int i=0;i<len1;++i) { for(int j=0;j<len2;++j) { //遍历字符串，如果当前字符相等，无需编辑操作，编译次数不变，不相等，需要编译一次 if(str1[i]==str2[j]) dp[i+1][j+1]=dp[i][j]; else dp[i+1][j+1]=min(dp[i][j],min(dp[i+1][j],dp[i][j+1]))+1; } } return dp[len1][len2]; } int main() { string str1,str2; while(getline(cin,str1)) { getline(cin,str2); cout<<calStringDistance(str1,str2)<<endl; } return 0; }

题目链接：https://www.nowcoder.com/questionTerminal/3959837097c7413a961a135d7104c314

 

注：如果本篇博客有任何错误和建议，欢迎伙伴们留言，你快说句话啊！