我的問題與Algorithm to transform one word to another through valid words相似用不同的字典編輯距離
但是與主要區別在於，我有一個固定的詞說「詹姆斯」和不同的詞典作爲我/ P。當然，我現在不能預處理字典。
所以我必須找到處理「JAMES」到「JOHNY」以不同詞典作爲輸入的最低成本。
是否有反正我可以預處理單詞「JAMES」，這樣我需要在運行時執行最少數量的編輯距離計算？你們有什麼建議？
首先，您需要正確定義您的規則 - 是允許添加或刪除多個字符，替換一個字符等的「編輯」？
無論如何 - 我只是從明顯的開始 - 創建一個圖表，其中每個單詞鏈接到所有可以直接編輯的單詞。然後，使用具有深度限制的遞歸，將訪問的元素標記爲「髒」以避免循環，然後查看是否存在單編輯解決方案，雙編輯解決方案等，直到找到解決方案或所有路徑在該深度爲髒。 （如果您在「髒」成員中記錄正在嘗試的深度，則不必擔心每次增加深度限制時清除它們，也可以標記所有髒子樹以避免再次遞歸到它們中）
我假設規則與您引用的問題類似，即一次只允許單個編輯，並且每個中間詞應該出現在給定的詞典中。
遞歸每個這話保持創建的每個唯一字節點。如果節點已經創建，只需創建邊。這完成了預處理。
現在給出一個字典，找到字典中的所有第一級字。對於所有的比賽，進一步找到所有的二級單詞等，直到你到達目的地單詞。