使用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']