Найти сложные слова в списке слов, используя Trie

Question

Учитывая список слов, я пытаюсь выяснить, как найти слова в этом списке, которые состоят из других слов в списке. Например, если список был ["race", "racecar", "car"], я хотел бы вернуть ["racecar"].

Вот мой общий мыслительный процесс. Я понимаю, что использование трии было бы хорошо для такого рода проблем. Для каждого слова я могу найти все его префиксы (это также слова в списке), используя trie. Затем для каждого префикса я могу проверить, состоит ли суффикс слова из одного или нескольких слов в trie. Однако мне сложно выполнять это. Я смог реализовать trie и функцию, чтобы получить все префиксы слова. Я просто застрял в реализации комплексного обнаружения слов.

Answer 1

Вы можете представить узлы Trie как defaultdict объекты, которые были расширены, чтобы содержать булевский флаг, если префикс является словом. Тогда вы могли бы иметь два обработки прохода, где на первом круге вы добавляете все слова TRIE и на втором раунде проверки для каждого слова, если это комбинация или нет:

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