查詢字典中所有有效字的算法問題

給定字典（只是字符串列表）。查詢字典中所有有效字的算法問題

您收到來自外部來源的未知數量字母的訂閱源。鑑於字母串，你將如何列出你可以從這些字母的任何組合中列出所有有效的單詞（從diciontary）。

因此，如果您收到：abpplead

你會發現蘋果，壞，墊，鉛等

我知道有沒有最佳答案。但什麼是一些合理有效的方式來做到這一點，使用什麼數據結構等。

此外，假設你可以預處理輸入，所以你可以選擇存儲輸入字母，因爲他們進來的任何數據你想要的結構。

來源

2009-10-30 Saobi

這與anagram代非常相似;比照http://stackoverflow.com/questions/55210/algorithm-to-generate-anagrams – 2009-10-30 03:13:57

將字典放入樹中。然後把這些字母放到一個由它們的字符值索引的計數器數組中，保持每個字母的計數（讓這個計數[]）。然後遍歷深度優先搜索順序，在向下遍歷時遞減每個字母的計數[字母]值，並在返回時遞增。現在，無論什麼時候重要的信件都要消極，停止並向上返回。任何時候你到達一個單詞終結者，輸出結果。

來源

2009-10-30 03:38:40

查詢字典中的每個單詞是否來自只有。
要檢查此您可以創建輔助結構像字典x[letter: amount]，與給定的字母，然後量初始化：

for each word 'w' in dictionary 
    init x from given letters 

    for each letter `ch` in word `w` 
     --x[ch] 
     if x[ch] < 0 
      break, do not add w to result 

    result.add(w)

來源

2009-10-30 03:17:14

簡單的蠻力算法。我在類似的情況下用python：在半秒內搜索一個355000字的字典。 – 2009-10-30 08:44:13

如果你不允許串的名單上執行任何預處理，然後沒有「合理有效的解決方案」：你將不得不在整個列表中迭代，檢查每個單詞是否可以根據需要組合（即，它的簽名，如下所示，一律小於傳入的簽名）。 O（N）爲列表中的N個字符串。

如果預處理被允許（你預處理列表一次，然後回答幾個查詢，足以分攤預處理成本），然後在列表中的每個字進行「簽名」，這是26點的整數計數的數組字符串中每個字母的出現（假設它是英文和不區分大小寫的 - 擴展名是顯而易見的）。隨着你走，從每個簽名到具有該簽名的單詞列表建立一個映射。這個預處理對於HashMap大致爲O（N）。

現在，給定一串K個字母，你可以計算一堆的簽名，並在地圖中查找每個帶有該簽名的單詞列表;對所有均勻一致的簽名重複（O（2^K）這裏是一個上限）。因此，對於Z這樣的查找，您需要支付O（N + Z * 2^K）（而不需要預處理）（O（Z * N）），所以您獲得了（對於足夠大的數字以便O（）估計有意義） -1K-。

來源

2009-10-30 03:19:28

1.爲字典中的每個單詞創建一個樹形結構。每個字母的樹枝，例如樹的第一級是字母a-z，下一級又是a-z如果有任何使用該組合的單詞等等。樹的葉子是單詞。

然後，當你得到的字母組合，正好與第一個字母都選擇開始，出行樹上下來分支，然後進行鍼對第二個字母都選擇一個搜索等

雖然這可能看起來很有用，因爲並非所有的combinatoins都是可能的，你會發現無效的分支很快被修剪掉了。

來源

2009-10-30 03:26:42

這被稱爲trie。當它們是唯一可能的選擇時，改進版本在同一節點中連接許多字母，這被稱爲基數樹。 – 2009-10-30 08:40:54

作爲一個已經爲基於規則的系統實現了Rete算法的人，我可以肯定地說這不是適合這個問題的算法。當存在大的工作記憶並且只有很小的增量變化時，Rete可以很好地工作，並且可以匹配很多模式。在這個問題中，工作記憶非常小（基本上是1個字）並且隨着每次匹配迭代而完全改變。 – 2009-10-31 00:30:39

-1

使用rete algorithm並將該問題視爲基於規則的域中的問題。單詞是規則（用自己的字母作爲規則模式）。對於給定的每一組字母，你應用規則庫和匹配的所有單詞將「激發」。沖洗並重復。 :)

[編輯]]

這裏的動機是這樣的：「Rete性能在理論上獨立於系統中規則的數量（在你的案例中的字典中）」。

來源

2009-10-30 03:32:54 alphazero

作爲一個爲基於規則的系統實現了Rete算法的人，我可以肯定地說這不是適合這個問題的算法。當存在大的工作記憶並且只有很小的增量變化時，Rete可以很好地工作，並且可以匹配很多模式。在這個問題中，工作記憶非常小（基本上是1個字）並且隨着每次匹配迭代而完全改變。 – 2009-10-31 00:31:46

將字典預處理爲dawg，然後使用其中一種dawg-walking算法來搜索子字符串。我有一些基本的Ruby代碼，用於處理dawg here;它在實踐中證明太慢，所以我轉向ocaml（未發佈），但它應該給你一個如何找到anagrams的想法。對於子標記，只需爲單詞結尾添加額外的檢查即使您的包不是空的。

來源

2009-10-30 07:13:24

查詢字典中所有有效字的算法問題

回答

相關問題