Implement trie (prefix tree)#

Levels: level-4

Data structures: trie

Practice Link#

Description#

Implement a trie with insert, search, and startsWith methods.
You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

Example#

1Trie trie = new Trie();
2
3trie.insert("apple");
4trie.search("apple");   // returns true
5trie.search("app");     // returns false
6trie.startsWith("app"); // returns true
7trie.insert("app");
8trie.search("app");     // returns true

Python Solution#

 1import collections
 2
 3
 4class TrieNode:
 5    # Initialize your data structure here.
 6    def __init__(self):
 7        self.children = collections.defaultdict(TrieNode)
 8        self.is_word = False
 9
10
11class Trie(object):
12    def __init__(self):
13        self.root = TrieNode()
14
15    def insert(self, word):
16        current = self.root
17        for letter in word:
18            current = current.children[letter]
19        current.is_word = True
20
21    def search(self, word):
22        current = self.root
23        for letter in word:
24            current = current.children.get(letter)
25            if current is None:
26                return False
27        return current.is_word
28
29    def startsWith(self, prefix):
30        current = self.root
31        for letter in prefix:
32            current = current.children.get(letter)
33            if current is None:
34                return False
35        return True
36
37
38# Your Trie object will be instantiated and called as such:
39# obj = Trie()
40# obj.insert(word)
41# param_2 = obj.search(word)
42# param_3 = obj.startsWith(prefix)