【出自BD笔试题】
难度系数：★★★★☆ 被考察系数：★★★★★
题目描述：
编辑距离又称Levenshtein距离，是指两个字符串之间由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符、插入一个字符或删除一个字符。请设计并实现一个算法来计算两个字符串的编辑距离，并计算其复杂度。在某些应用场景下，替换操作的代价比较高，假设替换操作的代价是插入和删除的两倍，算法该如何调整？
分析与解答：
本题可以使用动态规划的方法来解决，具体思路如下：
给定字符串s1和s2，首先定义一个函数D（i，j）（0＜=i＜=strlen（s1），0＜=j＜=strlen（s2）），用来表示第一个字符串s1长度为i的子串与第二个字符串s2长度为j的子串的编辑距离。从s1变到s2可以通过如下三种操作实现：
（1）添加操作。假设已经计算出D（i，j-1）的值（s1[0…i]与s2[0…j-1]的编辑距离），则D（i，j）=D（i，j-1）+1（s1长度为i的字串后面添加s2[j]即可）。
（2）删除操作。假设已经计算出D（i-1，j）的值（s1[0…i-1]到s2[0…j]的编辑距离），则D（i，j）=D（i-1，j）+1（s1长度为i的字串删除最后的字符s1[j]即可）。
（3）替换操作。假设已经计算出D（i-1，j-1）的值（s1[0…i-1]与s2[0…j-1]的编辑距离），如果s1[i]=s2[j]，则D（i，j）=D（i-1，j-1），如果s1[i]！=s2[j]，则D（i，j）=D（i-1，j-1）+1（替换s1[i]为s2[j]，或替换s2[j]为s1[i]）。
此外，D（0，j）=j且D（i，0）=i（从一个字符串变成长度为0的字符串的代价为这个字符串的长度）。
由此可以得出如下实现方式：对于给定的字符串s1和s2，定义一个二维数组D，则有以下几种可能性。(www.xing528.com)
（1）如果i==0，那么D[i，j]=j（0＜=j＜=strlen（s2））。
（2）如果j==0，那么D[i，j]=i（0＜=i＜=strlen（s1））。
（3）如果i＞0且j＞0，
（a）如果s1[i]==s2[j]，那么D（i，j）=min{edit（i-1，j）+1，edit（i，j-1）+1，edit（i-1，j-1）}。
（b）如果s1[i]！=s2[j]，那么D（i，j）=min{edit（i-1，j）+1，edit（i，j-1）+1，edit（i-1，j-1）+1}。
通过以上分析可以发现，对于第一个问题可以直接采用上述的方法来解决。对于第二个问题，由于替换操作是插入或删除操作的两倍，因此只需要修改如下条件即可：
如果s1[i]！=s2[j]，那么D（i，j）=min{edit（i-1，j）+1，edit（i，j-1）+1，edit（i-1，j-1）+2}。
根据上述分析，给出实现代码如下：
程序运行结果如下：
算法性能分析：
这种方法的时间复杂度与空间复杂度都为O（m*n）（其中，m和n分别为两个字符串的长度）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
