Find Compound Words In List Of Words Using Trie

Given a list of words, I am trying to figure out how to find words in that list that are made up of other words in the list. For example, if the list were ['race', 'racecar', 'car'

Solution 1:

You could present Trie nodes as defaultdict objects which have been extended to contain a boolean flag marking if the prefix is a word. Then you could have two pass processing where on the first round you add all the words to Trie and on second round check for each word if it's a combination or not:

from collections import defaultdict

classNode(defaultdict):
    def__init__(self):
        super().__init__(Node)
        self.terminal = FalseclassTrie():
    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 isNone:
                returnFalsereturn node.terminal

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

        node.terminal = Truedefis_combination(self, word):
        node = self.root
        for i, c inenumerate(word):
            node = node.get(c)
            ifnot node:
                break# If prefix is a word check if suffix can be foundif node.terminal and word[i+1:] in self:
                returnTruereturnFalse

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

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

Output:

['racecar']