Problem Statement

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.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into 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
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
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

Solution

The Trie below stores the following words:

  • apple
  • app
  • any
  • big
  • bin
  • bind
  • cat
    flowchart TD RT[root] N0[a] N1[p] N2[p*] N3[n] N4[y*] N5[b] N6[c] N7[l] N8[e*] N9[i] N10[g*] N11[a] N12[t*] N13[n*] N14[d*] RT-->N0 RT-->N5 RT-->N6 N0-->N1 N0-->N3 N3-->N4 N1-->N2 N2-->N7 N7-->N8 N5-->N9 N9-->N10 N6-->N11 N11-->N12 N9-->N13 N13-->N14
    A * indicates an end of word.
class Node:
    def __init__(self, char=""):
        self.char = char
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> Node:
        """
            T: O(M) | M = word length; N = number of keys in Trie
            S: O(M)
        """
        node = self.root
        # Traverse down the branch that spells out the word.
        # Add nodes to extend the branch as necessary.
        for char in word:
            if char in node.children:
                node = node.children[char]
            else:
                temp = Node(char)
                node.children[char] = temp
                node = temp
        # Set the is_end flag to true to mark the end of the word
        node.is_end = True
    
    def search(self, word: str) -> bool:
        """
            T: O(M)
            S: O(1)
        """
        node = self.root
        # Traverse down the branch whose path is spelled out by 
        # the word. If a char is not a key in the children hash 
        # map, we know that the word doesn't exist in the Trie.
        # If we get to the end of the branch and the is_end flag 
        # is False, we know that the word does not exist in the Trie.
        for char in word:
            if char in node.children:
                node = node.children[char]
            else:
                return False
        
        return node.is_end
    
    def startsWith(self, prefix: str) -> bool:
        """
            T: O(M)
            S: O(1)
        """
        node = self.root

        # If a path can be spelled out by the chars in prefix,
        # we have word that starts with prefix. If not, we don't.
        for char in prefix:
            if char in node.children:
                node = node.children[char]
            else:
                return False

        return True

Leetcode 208 Implement Trie (Prefix Tree)