Trie를 사용하여 단어 목록에서 복합 단어 찾기

Question

단어 목록이 주어지면 목록에서 다른 단어로 구성된 단어를 찾는 방법을 찾으려고합니다. 예를 들어, 목록이 ["race", "racecar", "car"] 인 경우 ["racecar"]을 반환하고 싶습니다.

여기 내 일반적인 생각 프로세스입니다. 나는 trie를 사용하는 것이 이런 종류의 문제에 도움이된다는 것을 이해합니다. 각 단어에 대해 트라이를 사용하여 모든 접두사 (목록의 단어)를 찾을 수 있습니다. 그런 다음 각 접두어에 대해 단어의 접미사가 트라이에서 하나 이상의 단어로 구성되어 있는지 확인할 수 있습니다. 그러나, 나는 이것을 구현하는 데 어려움을 겪고있다. 나는 단어의 모든 접두사를 얻기 위해 trie와 함수를 구현할 수 있었다. 복합 단어 검색을 구현하는 데 막 붙어 있습니다.

Answer 1

접두사가 단어 인 경우 부울 플래그 표시를 포함하도록 확장 된 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']