正文 第二百一五章 最短编辑距离
最新网址:www.88106.info
88106推荐各位书友阅读:编程之战正文 第二百一五章 最短编辑距离
(88106 www.88106.info) 听到经理的解释,杨成联想起了一个经典问题——求字符串的最短编辑距离。
这个所谓编辑,就是新增字符,修改字符,删除字符三种操作。
假如有A和B两个字符串,该怎么求它们之间的距离呢?
首先应该明确一点,这个距离是有限的。
就算A和B再长,他们的距离不会超过A,B的长度之和。
然后,就开始考虑如何把这个问题转换为规模较小的子问题吧!
如果A和B的第一个字符相同,那么第一个字符我们就不管了。
直接计算A第二个及以后字符组成的子串,和B第二个及以后字符组成的子串,它们之间的距离。
假设A为“man”,B为“made”。
它们第一个字符相同,那就去掉“m”,计算“an”和“ade”之间的距离。
而如果A和B的第一个字符不相同,那么我们就分别进行6个操作来尝试。
1.删除A第一个字符,计算A剩下的与B的距离。
2.删除B第一个字符,计算A和B剩下的距离。
3.修改A第一个字符,使之与B第一个字符相同,再计算A和B的距离。
4.修改B第一个字符,使之与A第一个字符相同,再计算A和B的距离。
5.新增A的第一个字符到B前面,再计算A和B的距离。
6.新增B的第一个字符到A前面,再计算A和B的距离。
这6个操作所得到的距离中,最短的加上1,就是最短编辑距离。
根据这样的思路,很快就可以完成一个递归程序。88106 www.88106.info
如果您中途有事离开,请按CTRL+D键保存当前页面至收藏夹,以便以后接着观看!
最新网址:www.88106.info