首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 互联网 >

[动态规划-三] 编辑距离-Edit Distance

2013-09-12 
[动态规划-3] 编辑距离-Edit Distance问题描述:我们定义了一套操作方法来把两个不相同的字符串变得相同,具

[动态规划-3] 编辑距离-Edit Distance
问题描述:我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
1.修改一个字符(如把“a”替换为“b”)。
2.增加一个字符(如把“abdd”变为“aebdd”)。
3.删除一个字符(如把“travelling”变为“traveling”)。

比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g“的方式来达到目的。上面的两种方案,都仅需要一次操作。

给定两个字符串,请找出使得两个字符串相同的最少编辑次数,即编辑距离。


问题分析:

假设给定两个字符串A[m],B[n],我们用E[i,j]来表示A[0---i]和B[o---j]之间的编辑距离,则:

E[i,j] = min{ E[i-1,j-1] ,E[i-1,j] + 1, E[i,j-1] + 1}, 当A[i] = B[j]时;

E[i,j] = min{ E[i-1,j-1] + 1, E[i-1,j] + 1, E[i, j-1] +1},当A[i] /= B[j]时。



热点排行