首页 > 试题广场 >

编辑距离，又称Levenshtein距离，是指两个子串之间，

[问答题]
编辑距离，又称Levenshtein距离，是指两个子串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。请尝试写出一个算法来计算两个字符串的编辑距离，并计算其复杂度？在某些应用场景下，替换操作的代价比较高，假设替换操作的代价是插入和删除的两倍， 算法该如何调整？
添加回答
mysterioussuperstar头像 mysterioussuperstar
发表于 2019-12-08 22:48:09 回复(1)
eagle头像 eagle
动态规划。

字符串 A, B, 记录结果为二维数组R[n][m] （其中n，m为A， B的长度）
A 变换到 B 可以通过 如下 3个操作：
  1. 添加。即已知A[0..i]变化到B[0..j-1]的最小操作次数，最后加上 B[j]即可。 R[[i][j] = R[i][j-1] + 1 (添加操作代价为1）
  2. 删除。即已知A[0..i-1]变化到B[0..j]的最小操作次数， 最后删掉A[i]即可。 R[i][j] = R[i-1][j] + 1（删除操作代价为1）
  3. 替换。即已知A[0..i-1]变化到B[0..j-1]的最小操作次数， 最后替换A[i]为B[j]即可。 R[i][j] = R[i-1][j-1] + 1（替换操作代价为1）
公式为： 
R[[i][j] = min ( R[i][j-1] + 1, R[i-1][j] + 1,  R[i-1][j-1] + 1) 

当i或者j为0时， 相应地值为字符串长度（因为从一个字符串变成长度为0的字符串的代价为这个字符串的长度）。
动态规划求出R[n][m]就可以了。

时间复杂度O（nm)， 空间复杂度O（nm）（其实就是计算出R[n][m]这个数组）

替换代价变为2的时候， 公式改为： 
R[[i][j] = min ( R[i][j-1] + 1, R[i-1][j] + 1,  R[i-1][j-1] + 2) 

发表于 2015-01-05 22:27:53 回复(0)
我叫杨小诺头像 我叫杨小诺
哈哈哈哈
发表于 2015-08-28 10:44:59 回复(0)
大漠苍鹰头像 大漠苍鹰
第一问：
该问题可使用动态规划进行解决：定义二维数组W[i][j],记录第一串的第i个和第二个串的第j个字符进行判断时候的编辑距离。
转移方程为：W[i][j] = MIN{W[i-1][j]+1, W[i-1][j-1]+k, W[i][j-1]+1}
其中k表示，如果A[i]==B[j],k=0,否则为1。

该算法复杂度为O（m*n），m、n分别为字符串A、B的长度。

第二问：
在上述转移方程中，W[i-1][j]+1和W[i][j-1]+1均代表了插入或删除的情况，而中间的W[i-1][j-1]+k代表了替换的情况。
因此将W[i][j]的值的意义进行一下修改，修改为代价的值即可，此时需要对k进行修改，因为插入删除的代价都可以当做1来看，那么，
k可以进行乘以2的修改，即k可能等于0，也可能是2，而不是第一问中的1了。
这样就可以避免替换操作的代价。
发表于 2015-02-19 14:21:19 回复(0)
提交观点

问题信息

动态规划 字符串 人人网
来自：人人网2015研发笔试卷C
上传者：樱花
难度：
4条回答 19495浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号