Implement Trie Prefix Tree

MEDIUM✓ CHIP-TIMEDLC #208 — FULL STATEMENT ↗

The drill: Build a structure that can insert words and then answer two questions fast: is this exact word in the set, and does any inserted word start with this prefix? Both answers should cost only the length of the query, never the number of words stored.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Build a small store for words that supports three operations: insert a word, check whether an exact word was inserted, and check whether any inserted word starts with a given prefix.

Insert never rejects a word — repeated inserts of the same word are harmless — and both lookup operations should scale with the length of the query being asked, not with how many words have been stored so far.

A prefix check only needs some inserted word to begin with the query text; it doesn't require that exact prefix to itself have been inserted as a complete word.

EX 01

Trie()

insert("apple")

search("apple") → true

search("app") → false

startsWith("app") → true

insert("app")

search("app") → true

PREFIX OF AN INSERTED WORD ISN'T A WORD UNTIL IT'S INSERTED ITSELF

EX 02

Trie()

insert("cat")

search("dog") → false

startsWith("ca") → true

UNRELATED QUERY MISSES, SHARED PREFIX HITS

EX 03

Trie()

insert("a")

search("ab") → false

startsWith("ab") → false

QUERY WALKS OFF THE END OF THE TRIE ENTIRELY

insert, search, and startsWith should all run proportional to query length
words and prefixes contain lowercase letters, generally short
the same word may be inserted more than once without effect
search demands an exact stored word; startsWith only needs a prefix match

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking every previously inserted word against a query works, but it re-reads words that don't even share a first letter with what you're looking for. What if related words shared how they're stored?

HINT 2 THE STRUCTURE

Words that share a prefix could share the same chain of nodes — one node per letter, branching only at the point where words actually differ.

HINT 3 ONE STEP FROM THE ANSWER

Build a tree of characters: insert walks or creates a child per letter and marks the final node as a complete word; search walks the same chain and checks that end-of-word flag; startsWith walks it and only checks that the walk never broke.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SHARED CHAINPATTERN · CHARACTER TRIEinsert cat, car, dog · then search + startsWith

STEP 1

Empty trie. We'll insert cat, car, dog, then test search and startsWith against shared prefixes.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/implement-trie-prefix-tree.py — RACE PACE

LANG ▸

PACE ▸

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


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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def _walk(self, s: str):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

TIME O(K) ALL OPSSPACE O(Σ CHARS INSERTED)PYTHON · RACE PACE · 30 LN

class Trie:
    def __init__(self):
        self.words = []

    def insert(self, word: str) -> None:
        self.words.append(word)

    def search(self, word: str) -> bool:
        return word in self.words

    def startsWith(self, prefix: str) -> bool:
        return any(w.startswith(prefix) for w in self.words)

TIME O(N·K) SEARCH/STARTSWITHSPACE O(N·K)PYTHON · TRAINING PACE · 12 LN

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord = false;
}

class Trie {
    private final TrieNode root = new TrieNode();

    public Trie() {
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isWord = true;
    }

    private TrieNode walk(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            node = node.children.get(c);
            if (node == null) {
                return null;
            }
        }
        return node;
    }

    public boolean search(String word) {
        TrieNode node = walk(word);
        return node != null && node.isWord;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }
}

TIME O(K) ALL OPSSPACE O(Σ CHARS INSERTED)JAVA · RACE PACE · 39 LN

class Trie {
    private final List<String> words = new ArrayList<>();

    public Trie() {
    }

    public void insert(String word) {
        words.add(word);
    }

    public boolean search(String word) {
        return words.contains(word);
    }

    public boolean startsWith(String prefix) {
        for (String w : words) {
            if (w.startsWith(prefix)) {
                return true;
            }
        }
        return false;
    }
}

TIME O(N·K) SEARCH/STARTSWITHSPACE O(N·K)JAVA · TRAINING PACE · 23 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED