First Post

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

   class TrieNode:
       """A node in the trie structure"""
       def __init__(self, char):
           self.char = char
           self.is_end = False
           self.counter = 0
           self.children = {}
       class Trie:
       """The trie object"""
       def __init__(self):
           self.root = TrieNode("")
       
       def insert(self, word):
           node = self.root
           for char in word:
               if char in node.children:
                   node = node.children[char]
               else:
                   new_node = TrieNode(char)
                   node.children[char] = new_node
                   node = new_node
           node.is_end = True
           node.counter += 1
       
       def dfs(self, node, prefix):
           if node.is_end:
               self.output.append((prefix + node.char, node.counter))
           for child in node.children.values():
               self.dfs(child, prefix + node.char)
       
       def query(self, x):
           self.output = []
           node = self.root
           for char in x:
               if char in node.children:
                   node = node.children[char]
               else:
                   return []
           self.dfs(node, x[:-1])
           return sorted(self.output, key=lambda x: x[1], reverse=True)

1
2
3
4
5
6
7
8

   t = Trie()
   t.insert("was")
   t.insert("word")
   t.insert("war")
   t.insert("what")
   t.insert("where")
   print(t.query("wh"))
   # Output: [('what', 1), ('where', 1)]