Teaching Kids Programming – Python Implementation of Trie Data Structure (Prefix Tree)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Trie (we pronounce “try”) or prefix tree is a tree data structure used to retrieve a key in a strings dataset. There are various applications of this very efficient data structure, such as autocomplete and spellchecker.

Implement the Trie class:
Trie() initializes the trie object.

1 2 3

void insert(String word);// inserts the string word to the trie. boolean search(String word);// returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix);// returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

void insert(String word);// inserts the string word to the trie.
boolean search(String word);// returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix);// returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:
Input

1 2	["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

1	[null, null, true, false, true, null, true]

[null, null, true, false, true, null, true]

Explanation

1 2 3 4 5 6 7

Trie trie = new Trie(); trie.insert("apple"); trie.search("apple");   // return True trie.search("app");     // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app");     // return True

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Given a list A of N strings, if each string is sized of M characters, and given another list B of T strings, where each sized is U characters. Find out how many strings in B are prefix of any string in A.

We can bruteforce – by checking each string in B to see if it is a prefix of any string in A, this is going to take O(T*U*N).

Slightly changing the scope of the question, if we are asking how many strings in B are the same / can be found in A, we can use a hash set to store all the strings in A which is O(NM) time and O(NM) space. And then checing each string to see if it appears in the hash table O(TU) overall is O(NM+TU). It takes O(M) or O(U) time to compute the hash of a strings.

We can use a Data Structure called Trie which is also known as Prefix Tree to store the prefix of words. Building it takes O(NM) time and O(NM) space. And checking if a string is a prefix in Trie takes O(U), and thus the overall complexity is O(NM + TU).

Python Implementation of Trie Data Structure (Prefix Tree)

Each Trie Node needs a boolean flag to tell if it is a leaf node – meaning if a word ends here. Then inserting, searching or startsWith needs to follow the characters by characters. We need to allocate the Trie Node on the fly when it is not in the Prefix Tree.

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
41
42
43
44
45

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}
        self.isLeaf = False
 
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self
        for i in word:
            if not i in cur.data:
                cur.data[i] = Trie()
            cur = cur.data[i]
        cur.isLeaf = True                        
 
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        cur = self
        for i in word:
            if not i in cur.data:
                return False
            cur = cur.data[i]
        return cur.isLeaf
        
    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        cur = self
        for i in prefix:
            if not i in cur.data:
                return False
            cur = cur.data[i]
        return True        
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}
        self.isLeaf = False

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self
        for i in word:
            if not i in cur.data:
                cur.data[i] = Trie()
            cur = cur.data[i]
        cur.isLeaf = True                        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        cur = self
        for i in word:
            if not i in cur.data:
                return False
            cur = cur.data[i]
        return cur.isLeaf
        
    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        cur = self
        for i in prefix:
            if not i in cur.data:
                return False
            cur = cur.data[i]
        return True        
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Trie Algorithms Implementations:

• Teaching Kids Programming – Python Implementation of Trie Data Structure (Prefix Tree)
• C++ Implementation of Trie Data Structure using Hash Map
• The Beginners’ Guide to Trie: How to Use the Trie in C++?
• Trie Class Data Structure in Python
• GoLang: Implement Trie (Prefix Tree)

–EOF (The Ultimate Computing & Technology Blog) —