第二百一五章 最短编辑距离
洛杉矶神探小说推荐阅读：娇软美人在末世封神了、世界末日之毒液、大佬的小人鱼揣崽跑路了、特案三组、腐烂国度之活下去、末日聚集地、一价氢氯钾钠银、御鬼者传奇、暗影熊提伯斯的位面之旅、这个文字冒险游戏绝对有毒、末世满级大佬有异能空间、从黑科技到超级工程、快穿之养老攻略
听到经理的解释，杨成联想起了一个经典问题——求字符串的最短编辑距离。
这个所谓编辑，就是新增字符，修改字符，删除字符三种操作。
假如有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，就是最短编辑距离。
根据这样的思路，很快就可以完成一个递归程序。
http://www.luoshanjishentan.com/yt29375/12946841.html
请记住本书首发域名：www.luoshanjishentan.com。洛杉矶神探手机版阅读网址：www.luoshanjishentan.com
这个所谓编辑，就是新增字符，修改字符，删除字符三种操作。
假如有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，就是最短编辑距离。
根据这样的思路，很快就可以完成一个递归程序。
http://www.luoshanjishentan.com/yt29375/12946841.html
请记住本书首发域名：www.luoshanjishentan.com。洛杉矶神探手机版阅读网址：www.luoshanjishentan.com