A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Here is the code for Trie Data structure written in Python
class Node:
def __init__(self):
self.children = [None] * 26
self.EOW = None # end of word
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = Node()
def _char_to_index(self, ch):
# private helper function
# Converts key current character into index
# use only 'a' through 'z' and lower case
return ord(ch) - ord('a')
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
root = self.root
for level in range(len(word)):
index = self._char_to_index(word[level])
if not root.children[index]:
root.children[index] = Node()
root = root.children[index]
root.EOW = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
root = self.root
length = len(word)
for level in range(length):
index = self._char_to_index(word[level])
if not root.children[index]:
return False
root = root.children[index]
return root is not None and root.EOW
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
root = self.root
length = len(prefix)
for level in range(length):
index = self._char_to_index(prefix[level])
if not root.children[index]:
return False
root = root.children[index]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# word = 'ajay'
# obj.insert(word)
# param_2 = obj.search('deed')
# print(param_2)
# param_3 = obj.startsWith('aj')
Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.