需要的最少操作次数

Question

我有一个问题，假设我有一个给定的字符串：“最好”，目标字符串是假设：“野兽”。然后我必须确定将给定字符串转换为目标字符串的操作次数，但是允许的操作是： 1.向字符串添加字符。 2.删除一个字符。 3.交换两个字符位置。 （应该明智地使用，我们只有一次交换的机会。）

在上面的情况下它是1. 我们如何解决这样的问题，它是一个什么样的问题？ 我是新手学习者。这种事情的

Answer 1

Levenshtein distance

Answer 2

一种广泛使用的措施被称为Levenshtein距离。

http://en.wikipedia.org/wiki/Levenshtein_distance

的WP页面还提到/链接到其他类似的概念。它基本上是将一个单词转换为另一个单词所需的编辑次数的度量。