Implement Trie (Prefix Tree) | Leetcode 208

Welcome to our deep dive on Implement Trie (Leetcode 208). A Trie (pronounced "try", from retrieval) is an incredibly powerful specialized tree-like data structure deployed broadly in real-world systems, specifically for autocomplete features, spell-checkers, and IP routing.

Problem Statement

A trie or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

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.

Approach: TrieNode Graph Structure

Unlike a traditional HashMap or HashSet that maps keys to a specific bucket for O(1) lookups, a Trie creates an explicit path mapping each individual character sequentially as nodes in a Tree.

A TrieNode object is surprisingly simple:

1. It contains a map (or an Array of size 26) of its children nodes.
2. It contains a boolean flag is_end, to signify whether a complete word validly terminates at this exact node.

For example, inserting the word "apple": We traverse root -> a -> p -> p -> l -> e. We mark the e node with is_end = true. If we then search for "app", we trace root -> a -> p -> p. The node p physically exists, but its is_end is false. Therefore, "app" is not a word in our dictionary, but it is a valid prefix!

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

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

    def insert(self, word: str) -> None:
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_end = True

    def search(self, word: str) -> bool:
        curr = self.root
        for char in word:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return curr.is_end

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for char in prefix:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return True

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (208)