动态规划实现编辑距离的计算

编辑距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
由于这个概念是俄罗斯科学家Vladimir Levenshtein在1965年提出的,因此编辑距离又称为Levenshtein Distance。这个是典型的动态规划问题,只要求出状态转移方程就很好解决了。
首先定义一个函数getDistance(String s1, String s2, int i, int j) i和j分别为字符串s1和s2的长度。我们列出状态转移方程(参考链接戳这里

editdistance

大致就是这样子了,不过还是感觉不是特别完美,等有空了思考下交换怎么玩吧。

——Snake

snake

作者: snake

我们需要为这个社会做一点贡献,失去了才懂得去珍惜。

《动态规划实现编辑距离的计算》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注