python - Find Compound Words in List of Words using Trie -

given list of words, trying figure out how find words in list made of other words in list. example, if list ["race", "racecar", "car"], want return ["racecar"].

here general thought process. understand using trie sort of problem. each word, can find of prefixes (that words in list) using trie. each prefix, can check see if word's suffix made of 1 or more words in trie. however, having hard time implementing this. have been able implement trie , and function prefixes of word. stuck on implementing compound word detection.

you present trie nodes defaultdict objects have been extended contain boolean flag marking if prefix word. have 2 pass processing on first round add words trie , on second round check each word if it's combination or not:

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()         word in it:             self.add_word(word)      def __contains__(self, word):         node = self.root         c in word:             node = node.get(c)             if node none:                 return false          return node.terminal      def add_word(self, word):         node = self.root         c in word:             node = node[c]          node.terminal = true      def is_combination(self, word):         node = self.root         i, c in enumerate(word):             node = node.get(c)             if not node:                 break             # if prefix word check if suffix can found             if node.terminal , word[i+1:] in self:                 return true          return false  lst = ["race", "racecar", "car"] t = trie(lst)  print([w w in lst if t.is_combination(w)]) 

output:

['racecar']