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.