LeetCode Solutions Blog

Implement Trie (Prefix Tree)

Number: 208

Difficulty: Medium

Paid? No

Problem Description

Implement a Trie (Prefix Tree) data structure that supports inserting words, searching for complete words, and checking if any word starts with a given prefix.

Key Insights

Use a tree-like structure where each node represents a character.
Each node stores its children in a dictionary (or hash map) for O(1) average time access.
Mark the end of a word with a boolean flag.
Insertion is done character by character, creating new nodes as needed.
Searching and checking prefixes follow traversals down the tree.

Space and Time Complexity

Time Complexity:

Insert: O(m) where m is the length of the word.
Search: O(m)
startsWith: O(m)

Space Complexity:

O(N * M) in the worst-case scenario, where N is the number of words and M is the average length of the words, due to storing each character in the Trie.

Solution

We implement the Trie using a node-based approach. Each TrieNode contains a hash map (or dictionary) of its children and a boolean indicating if the node marks the end of a word. The Trie class uses these nodes to build out the words character by character. The insert method traverses and builds the necessary nodes; the search method verifies that all characters exist in order and that the final node marks the end of a word; the startsWith method checks if the prefix exists in the Trie. No tricky edge cases exist beyond handling null or empty inputs, as constraints guarantee valid lowercase strings.

Code Solutions

class TrieNode:
    def __init__(self):
        # Dictionary to store child nodes and a flag for end of word.
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        # Initialize the Trie with the root node.
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        # Start from the root.
        node = self.root
        for char in word:
            # If character doesn't exist, add a new TrieNode.
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        # Mark the end of word.
        node.is_end_of_word = True
    
    def search(self, word: str) -> bool:
        # Traverse the Trie for each character.
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        # Returns True if word ends exactly here.
        return node.is_end_of_word
    
    def startsWith(self, prefix: str) -> bool:
        # Traverse checking for the prefix.
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True