爱看小说网

繁体版 简体版
爱看小说网 > 编程之战 > 第二百一五章 最短编辑距离

第二百一五章 最短编辑距离

章节错误,点此举报(免注册),举报后维护人员会在两分钟内校正章节内容,请耐心等待,并刷新页面。

听到经理的解释,杨成联想起了一个经典问题——求字符串的最短编辑距离。    这个所谓编辑,就是新增字符,修改字符,删除字符三种cao作。    假如有A和B两个字符串,该怎么求它们之间的距离呢?    首先应该明确一点,这个距离是有限的。    就算A和B再长,他们的距离不会超过A,B的长度之和。    然后,就开始考虑如何把这个问题转换为规模较小的子问题吧!    如果A和B的第一个字符相同,那么第一个字符我们就不管了。    直接计算A第二个及以后字符组成的子串,和B第二个及以后字符组成的子串,它们之间的距离。    假设A为“man”,B为“made”。    它们第一个字符相同,那就去掉“m”,计算“an”和“ade”之间的距离。

『加入书签,方便阅读』