使用Trie查找單詞列表中的複合詞

Question

給出一個單詞列表，我想弄清楚如何在列表中找到由列表中的其他單詞組成的單詞。例如，如果列表是["race", "racecar", "car"]，我想返回["racecar"]。

這是我的一般思考過程。我知道使用一個trie可以解決這類問題。對於每個單詞，我可以使用trie找到它的所有前綴（也是列表中的單詞）。然後，對於每個前綴，我可以檢查單詞的後綴是否由單詞中的一個或多個單詞組成。但是，我很難實現這一點。我已經能夠實現trie和和函數來獲取單詞的所有前綴。我只是堅持實施複合詞檢測。

Answer 1

如果前綴爲單詞，則可以將Trie節點呈現爲defaultdict已擴展爲包含布爾標誌標記的對象。然後，你可以有地方在第一輪添加的所有的話特里和第二輪檢查每個字兩遍處理，如果它是一個組合或不：

from collections import defaultdict 

class Node(defaultdict): 
    def __init__(self): 
     super().__init__(Node) 
     self.terminal = False 

class Trie(): 
    def __init__(self, it): 
     self.root = Node() 
     for word in it: 
      self.add_word(word) 

    def __contains__(self, word): 
     node = self.root 
     for c in word: 
      node = node.get(c) 
      if node is None: 
       return False 

     return node.terminal 

    def add_word(self, word): 
     node = self.root 
     for c in word: 
      node = node[c] 

     node.terminal = True 

    def is_combination(self, word): 
     node = self.root 
     for i, c in enumerate(word): 
      node = node.get(c) 
      if not node: 
       break 
      # If prefix is a word check if suffix can be found 
      if node.terminal and word[i+1:] in self: 
       return True 

     return False 

lst = ["race", "racecar", "car"] 
t = Trie(lst) 

print([w for w in lst if t.is_combination(w)]) 

輸出：

['racecar']