需要的最少操作次數

Question

我有一個問題，假設我有一個給定的字符串：「最好」，目標字符串是假設：「野獸」。然後我必須確定將給定字符串轉換爲目標字符串的操作次數，但是允許的操作是： 1.向字符串添加字符。 2.刪除一個字符。 3.交換兩個字符位置。 （應該明智地使用，我們只有一次交換的機會。）

在上面的情況下它是1. 我們如何解決這樣的問題，它是一個什麼樣的問題？ 我是新手學習者。這種事情的

Answer 1

Levenshtein distance

Answer 2

一種廣泛使用的措施被稱爲Levenshtein距離。

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

的WP頁面還提到/鏈接到其他類似的概念。它基本上是將一個單詞轉換爲另一個單詞所需的編輯次數的度量。