Implement Trie (Prefix Tree) (LeetCode 208)

The problem

Design a class Trie with three methods:

• insert(word) stores a word.
• search(word) returns True only if that exact word was inserted.
• startsWith(prefix) returns True if any inserted word begins with prefix.

All words use lowercase letters.

insert("apple")
search("apple")    -> True
search("app")      -> False
startsWith("app")  -> True

"app" is a prefix of a stored word, but nobody inserted "app" itself, so search says no and startsWith says yes.

How to think about it

Start with brute force. Keep the words in a list or a set. search is easy with a set, O(L) to hash a word of length L. But startsWith has to check every stored word, which is O(N·L) for N words. In a typeahead box that is called on every keystroke, that is far too slow.

The key insight: share the prefixes. Store words as paths in a tree where each edge is a character. apple and app share the nodes a → p → p. Now any operation only walks the characters of its argument, so it costs O(L), no matter how many words are stored.

Telling “word” from “prefix”. After walking a → p → p, how do you know whether app was inserted or is just part of apple? Put a sentinel key '$' in the node where a word ends. search needs the sentinel at the end of the walk; startsWith only needs the walk to succeed.

Which pattern is this? It is the trie itself, the base of every problem in this lesson. The tell is “prefix” or “starts with” over a set of words. In Python, a dict of dicts is the fastest trie to write: setdefault(c, {}) creates a child only if it is missing.

Approach

1. Keep root = {}.
2. insert(w): start at root; for each character, step into that child, creating it if missing. At the end, set '$'.
3. search(w): walk the characters. If a child is missing, return False. At the end, return whether '$' is in the node.
4. startsWith(p): the same walk, but return True at the end without checking '$'.

Solution

class Trie:
    def __init__(self): self.root = {}
    def insert(self, w):
        n = self.root
        for c in w: n = n.setdefault(c, {})   # create child only if missing
        n['$'] = True                          # mark a word end
    def search(self, w):
        n = self.root
        for c in w:
            if c not in n: return False
            n = n[c]
        return '$' in n                        # must be a full word
    def startsWith(self, p):
        n = self.root
        for c in p:
            if c not in n: return False
            n = n[c]
        return True                            # any path is enough
# insert("apple"); search("apple") -> True; search("app") -> False; startsWith("app") -> True

Dry run

Running the operations in order on a fresh Trie():

Notice that the second insert creates no new nodes. It only adds the end marker.

Complexity

• Time: O(L) per operation, where L is the length of the word or prefix. Each character is one dict lookup.
• Space: O(S) in total, where S is the total number of characters inserted. Shared prefixes reduce this in practice.

Edge cases and pitfalls

• Prefix vs word. The most common bug is returning True from search without checking '$', which makes search("app") wrong.
• Empty prefix. startsWith("") returns True because the walk never fails. That matches the usual definition.
• Inserting twice is harmless: the path exists and '$' is set again.
• Sentinel clash. '$' is safe because inputs are lowercase letters. If inputs could contain '$', use a class with an is_end field instead.

Related problems

• Design Add and Search Words Data Structure (LeetCode 211): the same trie, with a . wildcard in search.
• Map Sum Pairs (LeetCode 677): a trie that answers a sum over every key with a prefix.
• Search Suggestions System (LeetCode 1268): typeahead, the classic real-world use of a trie.