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

    听到经理的解释，杨成联想起了一个经典问题——求字符串的最短编辑距离。

    这个所谓编辑，就是新增字符，修改字符，删除字符三种cao作。

    假如有A和B两个字符串，该怎么求它们之间的距离呢？

    首先应该明确一点，这个距离是有限的。

    就算A和B再长，他们的距离不会超过A，B的长度之和。

    然后，就开始考虑如何把这个问题转换为规模较小的子问题吧！

    如果A和B的第一个字符相同，那么第一个字符我们就不管了。

    直接计算A第二个及以后字符组成的子串，和B第二个及以后字符组成的子串，它们之间的距离。

    假设A为“man”，B为“made”。

    它们第一个字符相同，那就去掉“m”，计算“an”和“ade”之间的距离。