Trie

 

Trie is an efficient information retrieval data structure.

Trie

Every node of Trie consists of multiple branches. Each branch presents a possible character of keys. We need to mark the last node of every key as end of word node.

 

class TrieNode:
 
	def __init__(self):
    	self.children = [None]*26
        self.isEndOfWord = False
        
class Trie:
 
	def __init__(self):
    	self.root = TrieNode()
        
    def _charToIndex(self, ch):
    	return ord(ch) - ord('a')
    
    def insert(self, key):
    	curr = self.root
        
        for li in range(len(key)):
        	i = self._charToIndex(key[li])
            
            if not curr.children[i] :
            	curr.children[i] = TrieNode()
            curr = curr.children[i]
            
        curr.isEndOfWord = True
        
    def search(self, key):
    	curr = self.root
        for li in range(len(key)):
        	i = self._charToIndex(key[li])
            if not curr.children[i] :
            	return False
            curr = curr.children[i]
        
        return curr != None and curr.isEndOfWord

 

Time complexity

- Insert: O(key_length)

- Search: O(key_length)

 

Space complexity

- O(ALPHABET_SIZE * key_length * N) where N is number of keys in Trie.

 

Hashmap version

class TrieNode :
    
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        curr = self.root
        for ch in word :
            if ch not in curr.children :
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
            
        curr.isEndOfWord = True
                

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        curr = self.root
        
        for ch in word :
            if ch not in curr.children :
                return False
            curr = curr.children[ch]
            
        return curr != None and curr.isEndOfWord
            
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curr = self.root
        for ch in prefix :
            if ch not in curr.children :
                return False
            curr = curr.children[ch]
            
        return True
        

 

Source :

GeeksForGeeks