如何以最少的編輯次數將一個字符串轉換爲另一個字符串？

Question

我在電話採訪中被問到了這個問題。

給定兩個字符串可以找到將一個字符串轉換爲另一個字符串所需的最少編輯次數。假設n和m是輸入字符串的長度，解決方案需要在java中實現並以O（n * m）運行。

實施例：
字符串：牛奶 - >啤酒
分鐘編輯：

Answer 1

對於不同長度的字符串，可以使用的Levenshtein距離： http://en.wikipedia.org/wiki/Levenshtein_distance

如果你有等長的字符串，你不想考慮插入或刪除，哈挖掘技術距離是更有效的： http://en.wikipedia.org/wiki/Hamming_distance

Levenshtein距離的示例實施方式： http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

Answer 2

假設：字包含不同字母。

如何爲S1創建字符哈希值。

現在遍歷S2中的每個字符並嘗試從S1的Hashset中移除它。如果你可以移除角色，不要增加計數器。否則增加計數器。

該計數器包含最少的編輯數量。