通過每次只更改一個字母將一個單詞轉換爲另一個單詞

鑑於相等的長度是在字典中的兩個字，寫方法通過一次改變僅一個信一個單詞轉換爲另一個字。您在每個步驟中獲得的新單詞必須位於字典中。

例子：

Input: DAMP, LIKE 
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

2012-07-16 devsda

編輯距離？這是功課嗎？ – 2012-07-16 17:45:21

這[wolfram博客文章]（http://blog.wolfram.com/2012/01/11/the-longest-word-ladder-puzzle-ever/）可以幫助你。 – Talon876 2012-07-16 17:50:41

作爲問題的側面提示：Levenshtein或任何其他編輯距離與每個中間詞必須位於詞典中的要求無關。編輯距離無論如何都是微不足道的，因爲插入和刪除是被禁止的。 – thiton 2012-07-16 17:51:07

嘗試在graphs角度來思考這個問題：考慮在字典中的頂點的所有單詞，然後插入只有一個字母不同，每兩個頂點之間的邊緣。輸出是圖中衆所周知的對象，並且您可能已經知道解決該問題的算法。

擾流：

的輸出是在圖中的路徑，並且該問題是通過找到一個路徑來解決。 A breadth-first search（BFS）或Dijkstra's algorithm優雅地解決問題。

2012-07-16 17:48:01 thiton

這很有可能是OP不知道有關節點或圖形的任何信息。什麼是「邊緣」？ – 2012-07-16 17:50:32

@RobertHarvey：感謝您的建議，鏈接到維基百科來定義基本概念。 – thiton 2012-07-16 18:06:15

主席先生，您能否詳細說明如何以時間有效的方式將圖表從字典中刪除。 – devsda 2012-09-02 21:54:56

回答